《实验八 图的应用》由会员分享，可在线阅读，更多相关《实验八 图的应用（14页珍藏版）》请在金锄头文库上搜索。
1、1实验八实验八 图的应用图的应用( (设计性实验设计性实验) )一、实验目的一、实验目的通过最短路径算法的实现，掌握图的存储结构特点和有关图的基本操作。二、实验准备二、实验准备1. 图的定义和基本术语；2. 图的四种存储结构（数组表示法、邻接表、十字链表和邻接多重表） ；3. 图的两种遍历策略（深度优先搜索和广度优先搜索深度优先搜索和广度优先搜索） ，并应该注意图的遍历和树的遍历算法之间的区别；4. 图的连通性、连通分量和最小生成树的概念和实现方法；5. 拓扑排序和关键路径、两类求最短路径问题的解法。6.部分相关代码： 图的结构定义（这里使用数组表示法）#define infinity 100
2、00#define max_vertex_num 20typedef int vrtype;typedef enum dg,dn,udg,udngraphkind;typedef struct arccell vrtype adj;infotype *info;adjmatrixmax_vertex_num max_vertex_num;typedef struct vertextype vexsmax_vertex_num;adjmatrix arcs;int vexnum,arcnum;2graphkind kind; mgraph; 迪杰斯特拉算法 void shortestpath_d
3、ij(mgraph g,int v0,pathmatrix p,shortpathtable d) for( v=0;v #define N 20 #define TRUE 1 #define FALSE 0 int visitedN; typedef struct /*队列的定义*/ int dataN;int front,rear; queue;typedef struct /*图的邻接矩阵*/4int vexnum,arcnum;char vexsN;int arcsNN; graph;void createGraph(graph *g); /*建立一个无向图的邻接矩阵*/ void d
4、fs(int i,graph *g); /*从第 i 个顶点出发深度优先搜索*/ void tdfs(graph *g); /*深度优先搜索整个图*/ void bfs(int k,graph *g); /*从第 k 个顶点广度优先搜索*/ void tbfs(graph *g); /*广度优先搜索整个图*/ void init_visit(); /*初始化访问标识数组*/void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/ int i,j;char v;g-vexnum=0;g-arcnum=0;i=0;printf(“输入顶点序列(以#结束)：n“);wh
5、ile(v=getchar()!=#)g-vexsi=v; /*读入顶点信息*/i+;g-vexnum=i; /*顶点数目*/for(i=0;ivexnum;i+) /*邻接矩阵初始化*/for(j=0;jvexnum;j+)g-arcsij=0;printf(“输入边的信息：n“);scanf(“%d,%d“, /*读入边 i,j*/while(i!=-1) /*读入 i,j 为1 时结束*/g-arcsij=1;g-arcsji=1;scanf(“%d,%d“,5void dfs(int i,graph *g) /*从第 i 个顶点出发深度优先搜索*/ int j;printf(“%c“,
6、g-vexsi);visitedi=TRUE;for(j=0;jvexnum;j+)if(g-arcsij=1) void tdfs(graph *g) /*深度优先搜索整个图*/ int i;printf(“n 从顶点%C 开始深度优先搜索序列：“,g-vexs0);for(i=0;ivexnum;i+)if(visitedi!=TRUE)dfs(i,g); void bfs(int k,graph *g) /*从第 k 个顶点广度优先搜索*/ int i,j;queue qlist,*q;q=q-rear=0;q-front=0;printf(“%c“,g-vexsk);visitedk=
7、TRUE;q-dataq-rear=k;q-rear=(q-rear+1)%N;while(q-rear!=q-front)i=q-dataq-front;q-front=(q-front+1)%N;for(j=0;jvexnum;j+)if(g-arcsij=1)visitedj=TRUE;q-dataq-rear=j;q-rear=(q-rear+1)%N; void tbfs(graph *g) /*广度优先搜索整个图*/ int i;printf(“n 从顶点%C 开始广度优先搜索序列：“,g-vexs0);for(i=0;ivexnum;i+)if(visitedi!=TRUE)bf
8、s(i,g); void init_visit() /*初始化访问标识数组*/ int i;for(i=0;i #include #define N 20typedef struct edgenode /*图的邻接表：邻接链表结点*/int adjvex; /*顶点序号*/struct edgenode *next; /*下一个结点的指针*/ edgenode;typedef struct vnode /*图的邻接表：邻接表*/char data; /*顶点信息*/int ind; /*顶点入度*/struct edgenode *link; /*指向邻接链表指针*/ vnode;void c
9、reateGraph_list(vnode adjlist,int *p)； /*建立有向图的邻接 表*/ void topSort(vnode g,int n)； /*拓扑排序*/ABCDEFGH0 01 12 23 34 45 56 67 78void createGraph_list(vnode adjlist,int *p) /*建立有向图的邻接 表*/int i,j,n,e;char v;edgenode *s;i=0;n=0;e=0;printf(“输入顶点序列(以#结束)：n“);while(v=getchar()!=#)adjlisti.data=v; /*读入顶点信息*/ad
10、jlisti.link=NULL;adjlisti.ind=0;i+;n=i;*p=n;/*建立邻接链表*/printf(“n 请输入弧的信息(i=-1 结束)：i,j:n“);scanf(“%d,%d“,while(i!=-1)s=(struct edgenode*)malloc(sizeof(edgenode);s-adjvex=j;s-next=adjlisti.link;adjlisti.link=s;adjlistj.ind+; /*顶点 j 的入度加 1*/e+;scanf(“%d,%d“,printf(“邻接表:“);for(i=0;i%d“,s-adjvex);s=s-next
11、; 9void topSort(vnode g,int n) /*拓扑排序*/int main()vnode adjlistN;int n,*p;p=createGraph_list(adjlist,p);return 0; 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入: ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1运行结果：103、阅读并运行下面程序。 #include #define N 20 #define TRUE 1#define INF 32766 /*邻接矩阵中的无穷大元素*/ #define INFIN 32767 /*比无穷大元素大的数*/ty
12、pedef struct /*图的邻接矩阵*/int vexnum,arcnum;char vexsN;int arcsNN; graph;void createGraph_w(graph *g,int flag); void prim(graph *g,int u); void dijkstra(graph g,int v); void showprim(); void showdij();/*建带权图的邻接矩阵,若 flag 为 1 则为无向图，flag 为 0 为有向图*/ void createGraph_w(graph *g,int flag) int i,j,w;char v;g-
13、vexnum=0;g-arcnum=0;i=0;printf(“输入顶点序列(以#结束)：n“);while(v=getchar()!=#)g-vexsi=v; /*读入顶点信息*/i+;g-vexnum=i;11for(i=0;iarcsij=INF;printf(“输入边的信息：n“);scanf(“%d,%d,%d“, /*读入边(i,j,w)*/while(i!=-1) /*读入 i 为1 时结束*/g-arcsij=w;if(flag=1)g-arcsji=w;scanf(“%d,%d,%d“, void prim(graph *g,int u)/*出发顶点 u*/ int lowc
14、ostN,closestN,i,j,k,min;for(i=0;ivexnum;i+) /*求其他顶点到出发顶点 u 的权*/lowcosti=g-arcsui;closesti=u;lowcostu=0;for(i=1;ivexnum;i+) /*循环求最小生成树中的各条边*/ min=INFIN;for(j=0;jvexnum;j+) /*选择得到一条代价最小的边*/if(lowcostj!=0 /*输出该边*/lowcostk=0; /*顶点 k 纳入最小生成树 */for(j=0;jvexnum;j+) /*求其他顶点到顶点 k 的权*/if(g-arcskj!=0closestj=k;12 void dijkstra(graph g,int v) /*dijkstra 算法求单源最短路径*/int pathNN,distN,sN;int mindis,i,j,u,k;for(i=0;i到各顶点的最短路径n“,g.vexsv);for(i=0;i顶点%c：“,g.vexsv,g.vexsi);13if(disti=INF)printf(“无路径“);elseprintf(“%d “,disti);printf(“经过顶点：“);for(j=0;j%c“,g.vexsj);printf(“-%cn“,g.vexsi); void showprim()/*最小生成
