最短路径与最小生成树

[键入文字]

数 据 结 构

实验报告

姓 名： 邱金梁

班 级： rJBJava101

学 号： [1**********]7

指导老师： 杨 关

时 间： 2012年6月13日

一 、最小生成树

#include//头文件 using namespace std;

#define MAX_VERTEX_NUM 20//最大结点数 #define MAX 200

typedef struct Close//结构体 {

char adjvex; int lowcost;

}Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode {

int adjvex; ArcNode *nextarc; int info; }ArcNode;

typedef struct VNode { char data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct {

AdjList verties; int vexnum,arcnum;

}ALGraph;

ALGraph G;//对象G

int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数

void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G);

/*for(int i=1;i

for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)

coutadjvex].datainfo

}*/

while(i)

{ cout>a; MinSpanTree_PRIM(G,a);

cout>i; } return 0; }

int LocateVek(ALGraph G,char u) {

int i; for(i=1;i

if(u==G.verties[i].data)

return i;

return -1; }

int minimum(close m)//返回最小数 { int i=0,j,n=200;

for(i=1;i

}

j=i;

return j; }

void MinSpanTree_PRIM(ALGraph G,char u) { int j,k,a;

close closedge;ArcNode *s,*p,*q; for(j=1;j

closedge[j].lowcost=MAX;//把所有值都赋为最大 k=LocateVek(G,u); for(j=1;j

if(j!=k)

{

closedge[j].adjvex=u;

for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc) if(j==s->adjvex)

{closedge[j].lowcost=s->info; break;

}

}

closedge[k].lowcost=0;

cout

k=minimum(closedge);

cout

for(p=G.verties[k].firstarc;p!=NULL;p=p->nextarc) if(p->infoadjvex) { }

closedge[i].adjvex=G.verties[k].data; closedge[i].lowcost=p->info;

}cout

cout=1;j--) { if(closedge[j].lowcost==0&&G.verties[j].data!=u) { cout

a=closedge[j].adjvex; for(q=G.verties[j].firstarc;q!=NULL;q=q->nextarc) if(a-64==q->adjvex) }

coutinfo

void Create(ALGraph &G) {

int i,j,k,x;

char a,b;ArcNode *s; cout>G.vexnum; cout

cin>>G.arcnum; cout

cin>>G.verties[i].data; G.verties[i].firstarc=NULL; } for(i=1;i

}

cout>a>>b;cin>>x;

j=a-64;k=b-64;//将字符型转化成整数型 s=new ArcNode; s->info=x; s->adjvex=k;

s->nextarc=G.verties[j].firstarc; G.verties[j].firstarc=s; s=new ArcNode; s->info=x;

s->adjvex=j;

s->nextarc=G.verties[k].firstarc; G.verties[k].firstarc=s;

二、最短路径

#include #include #include #include using namespace std;

enum Mark {UNVISITED,VISITED};

typedef struct DocuNode {

int n; Mark m; } DocuNode;

typedef struct Docu { int n;

DocuNode * Node; int** edge; } Docu;

Mark getMark(Docu*D , int i) {

return D->Node[i].m; }

void setMark(Docu*D,int v,Mark m) {

D->Node[v].m=m; }

int first(Docu*D , int v) {

int i;

for(i=0 ; in ; i++) if((D->edge[v][i])!=-1) return i; return i; }

int next(Docu*D , int v , int w) {

int i;

for(i=w+1 ; in ; i++) if((D->edge[v][i])!=-1) return i; return i; }

int weight(Docu*D,int v,int w) {

return D->edge[v][w]; }

int minV ertex(Docu*D , int *B) {

int i , v;

for(i=0; in; i++)

if(getMark(D,i)==UNVISITED) { v=i;

break; }

for(i++; in; i++)

if(getMark(D,i)==UNVISITED&&((((B[i]

return v; }

void Dijkstra(Docu*D , int *B , int s) {

int i,v,w;

for(i=0; in; i++) {

v=minVertex(D,B); if(B[v]==-1) return;

setMark(D,v,VISITED);

for(w=first(D,v); wn; w=next(D,v,w)) if((B[w]>(B[v]+weight(D,v,w)))||(B[w]==-1)) B[w]=B[v]+weight(D,v,w); } }

int main()

{

Docu* D;

ifstream fin("Docu.txt"); int i , j;

D=(Docu*)malloc(sizeof(Docu)); fin>>D->n;//从文件中读取节点数

D->Node=(DocuNode*)malloc(sizeof(DocuNode));

for(i=0 ; in ; i++)

D->Node[i].m=UNVISITED; //将所有节点设为未被访问的

D->edge=(int**)calloc(1,sizeof(int*)*D->n); if(!D->edge) //若内存未分配成功 coutn ; i++)

{

D->edge[i]=(int*)calloc(1,sizeof(int)*D->n); if(!D->edge[i]) //若内存未分配成功 cout

for(i=0 ; in ; i++)

for(j=0 ; jn ; j++)

fin>>D->edge[i][j]; //从文件中读取边权值

int start , end;

cout>start;

cout>end;

int *B;

B=(int *)malloc(D->n*sizeof(int));

for(i=0 ; in ; i++) B[i]=D->edge[start][i];

Dijkstra(D,B,start);

cout

}

[键入文字]

数 据 结 构

实验报告

姓 名： 邱金梁

班 级： rJBJava101

学 号： [1**********]7

指导老师： 杨 关

时 间： 2012年6月13日

一 、最小生成树

#include//头文件 using namespace std;

#define MAX_VERTEX_NUM 20//最大结点数 #define MAX 200

typedef struct Close//结构体 {

char adjvex; int lowcost;

}Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode {

int adjvex; ArcNode *nextarc; int info; }ArcNode;

typedef struct VNode { char data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct {

AdjList verties; int vexnum,arcnum;

}ALGraph;

ALGraph G;//对象G

int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数

void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G);

/*for(int i=1;i

for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)

coutadjvex].datainfo

}*/

while(i)

{ cout>a; MinSpanTree_PRIM(G,a);

cout>i; } return 0; }

int LocateVek(ALGraph G,char u) {

int i; for(i=1;i

if(u==G.verties[i].data)

return i;

return -1; }

int minimum(close m)//返回最小数 { int i=0,j,n=200;

for(i=1;i

}

j=i;

return j; }

void MinSpanTree_PRIM(ALGraph G,char u) { int j,k,a;

close closedge;ArcNode *s,*p,*q; for(j=1;j

closedge[j].lowcost=MAX;//把所有值都赋为最大 k=LocateVek(G,u); for(j=1;j

if(j!=k)

{

closedge[j].adjvex=u;

for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc) if(j==s->adjvex)

{closedge[j].lowcost=s->info; break;

}

}

closedge[k].lowcost=0;

cout

k=minimum(closedge);

cout

for(p=G.verties[k].firstarc;p!=NULL;p=p->nextarc) if(p->infoadjvex) { }

closedge[i].adjvex=G.verties[k].data; closedge[i].lowcost=p->info;

}cout

cout=1;j--) { if(closedge[j].lowcost==0&&G.verties[j].data!=u) { cout

a=closedge[j].adjvex; for(q=G.verties[j].firstarc;q!=NULL;q=q->nextarc) if(a-64==q->adjvex) }

coutinfo

void Create(ALGraph &G) {

int i,j,k,x;

char a,b;ArcNode *s; cout>G.vexnum; cout

cin>>G.arcnum; cout

cin>>G.verties[i].data; G.verties[i].firstarc=NULL; } for(i=1;i

}

cout>a>>b;cin>>x;

j=a-64;k=b-64;//将字符型转化成整数型 s=new ArcNode; s->info=x; s->adjvex=k;

s->nextarc=G.verties[j].firstarc; G.verties[j].firstarc=s; s=new ArcNode; s->info=x;

s->adjvex=j;

s->nextarc=G.verties[k].firstarc; G.verties[k].firstarc=s;

二、最短路径

#include #include #include #include using namespace std;

enum Mark {UNVISITED,VISITED};

typedef struct DocuNode {

int n; Mark m; } DocuNode;

typedef struct Docu { int n;

DocuNode * Node; int** edge; } Docu;

Mark getMark(Docu*D , int i) {

return D->Node[i].m; }

void setMark(Docu*D,int v,Mark m) {

D->Node[v].m=m; }

int first(Docu*D , int v) {

int i;

for(i=0 ; in ; i++) if((D->edge[v][i])!=-1) return i; return i; }

int next(Docu*D , int v , int w) {

int i;

for(i=w+1 ; in ; i++) if((D->edge[v][i])!=-1) return i; return i; }

int weight(Docu*D,int v,int w) {

return D->edge[v][w]; }

int minV ertex(Docu*D , int *B) {

int i , v;

for(i=0; in; i++)

if(getMark(D,i)==UNVISITED) { v=i;

break; }

for(i++; in; i++)

if(getMark(D,i)==UNVISITED&&((((B[i]

return v; }

void Dijkstra(Docu*D , int *B , int s) {

int i,v,w;

for(i=0; in; i++) {

v=minVertex(D,B); if(B[v]==-1) return;

setMark(D,v,VISITED);

for(w=first(D,v); wn; w=next(D,v,w)) if((B[w]>(B[v]+weight(D,v,w)))||(B[w]==-1)) B[w]=B[v]+weight(D,v,w); } }

int main()

{

Docu* D;

ifstream fin("Docu.txt"); int i , j;

D=(Docu*)malloc(sizeof(Docu)); fin>>D->n;//从文件中读取节点数

D->Node=(DocuNode*)malloc(sizeof(DocuNode));

for(i=0 ; in ; i++)

D->Node[i].m=UNVISITED; //将所有节点设为未被访问的

D->edge=(int**)calloc(1,sizeof(int*)*D->n); if(!D->edge) //若内存未分配成功 coutn ; i++)

{

D->edge[i]=(int*)calloc(1,sizeof(int)*D->n); if(!D->edge[i]) //若内存未分配成功 cout

for(i=0 ; in ; i++)

for(j=0 ; jn ; j++)

fin>>D->edge[i][j]; //从文件中读取边权值

int start , end;

cout>start;

cout>end;

int *B;

B=(int *)malloc(D->n*sizeof(int));

for(i=0 ; in ; i++) B[i]=D->edge[start][i];

Dijkstra(D,B,start);

cout

}


相关内容

  • 最小生成树and最短路径

    • 最小生成树and 最短路径 无独有偶,在两个学期的期末中两门不同的科目<离散数学>和<数据结构>中都谈到了图及其衍生的最小生成树.最短路径问题,并给出了相应的算法--克鲁斯卡尔.普林.迪杰斯特拉.沃舍尔算法.这无疑是释放了一个很大的信号--这些内容很重要.由于之前学<离 ...

  • 公园内道路设计问题

    • 公园内道路设计问题· 摘要 公园内道路设计问题本质上是最短路径问题,该问题是现实生活中常见的的研究课题,在商业利润估算.生产生活.运输路线选择等方面都有重要意义.本文对公园内道路设计问题进行建模.求解及相关分析. 对于问题一,根据题目中两个原则:边界道路不计入修建道路总长及最短道路长不大于两点连线1 ...

  • 最短路径最少费用数学建模论文

    • 摘 要 现今社会网络越来越普及,网购已成为一种常见的消费方式,随之物流行业也渐渐兴盛,每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位,即高质量高速度的完成送货任务,针对本案例,我们采用了大量的科学分析方法,并进行了反复验证,得出如下结果: 问题1:根据所给问题与数据,我们将题目中给出的 ...

  • 离散数学实验

    • 实验一 油管铺设 实验准备 最小生成树问题,求最小生成树的Prim 算法 实验目的 运用最小生成树思想和求最小生成树程序解决实际问题 实验过程 八口海上油井相互间距离如下表,其中1号井离海岸最近,为5km .问从海岸经1号井铺设油管把各井连接起来,怎样连油管长度最短(为便于检修,油管只准在油井处分叉 ...

  • 人工智能启发式图搜索算法

    • 启发式图搜索算法 摘 要:启发式搜索策略概述和有序搜索.启发式搜索弥补盲目搜索的不足,提高搜索效率.一种方法用于排列待扩展节点的顺序,即选择最有希望的节点加以扩展,那么,搜索效率将会大为提高.进行搜索技术一般需要某些有关具体问题领域的特性的信息. 关键词:启发式搜索:估价函数:有序搜索:A*算法: ...

  • 图论算法(经典)

    • 图论算法 最小生成树算法(Prim算法) 单源最短路径算法(Dijkstra算法) 任意结点最短路径算法(Floyd算法) 求有向带权图的所有环 Bellman-Ford 算法 计算图的连通性 计算最佳连通分支 计算拓扑序列 图论算法习题 网络建设问题 最短变换问题 挖地雷 乌托邦城市 乌托邦交通中 ...

  • 继电保护整定计算软件功能介绍

    • 继电保护整定计算软件功能介绍 软件功能介绍 (1).图形绘制及打印 绘制并存储以下发电厂的电气元件发电机.外部等效系统.两绕组变压器.三绕组变压器.自耦变压器.线路.电抗器.分裂电抗器.电容器.电动机.断路器.母线.连线. (2).图形编辑 电气元件设备可移动.旋转.缩放.镜像(对三端元件).文字标 ...

  • 博超电力电气工程设计软件技术协议

    • 电力电气设计软件技术协议 博超变电设计软件技术协议 1标准技术参数 表1 标准技术参数表 2.使用条件 表3 使用条件表 3软件优势.特点 3.1市场优势 北京博超时代软件系列产品EES系列电力电气设计软件产品EESV11.0P适用 范围为:1000kV-380/220V供配电系统接线图.控制原理图 ...

  • 栅格数据空间分析

    • GIS 空间分析方法 (第二部分 栅格数据空间分析) 一.知识点介绍 1.邻域分析 (1)目的 掌握局部分析和邻域分析的基本方法和操作步骤. (2)数据 -\实验数据\栅格数据分析\知识点介绍\邻域分析 (3)操作 邻域分析: 邻域统计的计算是以待计算栅格为中心,向其周围扩展一定范围,基于这些扩展栅 ...

热门内容

标签

医院催款通知书范文   乡村小学简介范文   诚信承诺书范文   博士入学申请书范文   四级必背范文   英语长对话范文   转正答辩ppt范文   工作人员自传范文   中式餐厅设计说明范文   侵占罪诉状   休假请假邮件   新上任乡镇长表态发言   心理健康演讲稿300字