实验7 图的表示与遍历.docx

1、实验7 图的表示与遍历 实验五 图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法 3、理解图的应用方法二、实验预习说明以下概念1、深度优先搜索遍历：从根开始一个一个搜索2、广度优先搜索遍历：从根的邻接点出发依次访问3、拓扑排序： 一个无指向的点开始排序4、最小生成树： 最小权的生成树5、最短路径： 路径权数最小三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include#define N 20#define TRUE 1#define FALSE 0int visitedN; typedef struct /*队列的定义*/

2、int dataN; int front,rear;queue;typedef struct /*图的邻接矩阵*/ int vexnum,arcnum; char vexsN; int arcsNN;graph;void createGraph(graph *g); /*建立一个无向图的邻接矩阵*/void dfs(int i,graph *g); /*从第i个顶点出发深度优先搜索*/void tdfs(graph *g); /*深度优先搜索整个图*/void bfs(int k,graph *g); /*从第k个顶点广度优先搜索*/void tbfs(graph *g); /*广度优先搜索整

3、个图*/void init_visit(); /*初始化访问标识数组*/void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/ int i,j; char v; g-vexnum=0; g-arcnum=0; i=0; printf(输入顶点序列(以#结束)：n); while(v=getchar()!=#) g-vexsi=v; /*读入顶点信息*/ i+; g-vexnum=i; /*顶点数目*/ for(i=0;ivexnum;i+) /*邻接矩阵初始化*/ for(j=0;jvexnum;j+) g-arcsij=0; printf(输入边的信息：n);

4、 scanf(%d,%d,&i,&j); /*读入边i,j*/ while(i!=-1) /*读入i,j为1时结束*/ g-arcsij=1; g-arcsji=1; scanf(%d,%d,&i,&j); void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/ int j; printf(%c,g-vexsi); visitedi=TRUE; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) dfs(j,g);void tdfs(graph *g) /*深度优先搜索整个图*/ int i; printf(n从顶点%C

5、开始深度优先搜索序列：,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=&qlist; q-rear=0; q-front=0; printf(%c,g-vexsk); visitedk=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)%

6、N; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) printf(%c,g-vexsj); 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) bfs(i,g);void init_visit() /*初始化访问标识数组*/ int i; for(i=0;iN;i+)

7、visitedi=FALSE;int main() graph ga; int i,j; createGraph(&ga); printf(无向图的邻接矩阵：n);for(i=0;iga.vexnum;i+) for(j=0;jga.vexnum;j+) printf(%3d,ga.arcsij); printf(n); init_visit(); tdfs(&ga); init_visit(); tbfs(&ga); return 0; 根据右图的结构验证实验，输入：ABCDEFGH#0,10,20,51,31,42,52,63,74,7-1,-1 运行结果：2、阅读并运行下面程序，补充拓扑

8、排序算法。#include#include#define N 20typedef struct edgenode /*图的邻接表：邻接链表结点*/ int adjvex; /*顶点序号*/ struct edgenode *next; /*下一个结点的指针*/edgenode;typedef struct vnode /*图的邻接表：邻接表*/ char data; /*顶点信息*/ int ind; /*顶点入度*/ struct edgenode *link; /*指向邻接链表指针*/vnode;void createGraph_list(vnode adjlist,int *p)； /*

9、建立有向图的邻接表*/void topSort(vnode g,int n)； /*拓扑排序*/void 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; /*读入顶点信息*/ adjlisti.link=NULL; adjlisti.ind=0; i+; n=i; *p=n; /*建立邻接链表*/ printf(n请输入

10、弧的信息(i=-1结束)：i,j:n); scanf(%d,%d,&i,&j); 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,&i,&j); printf(邻接表:); for(i=0;i%d,s-adjvex); s=s-next; void topSort(vnode g,int n) /*拓扑排序*/int main() vnod

11、e adjlistN; int n,*p; p=&n; createGraph_list(adjlist,p); return 0; 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入:ABCDEF#0,11,22,34,14,5-1,-1 运行结果：3、阅读并运行下面程序。#include#define N 20#define TRUE 1#define INF 32766 /*邻接矩阵中的无穷大元素*/#define INFIN 32767 /*比无穷大元素大的数*/typedef struct /*图的邻接矩阵*/ int vexnum,arcnum; char vexsN; int

12、 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-vexnum=0; g-arcnum=0; i=0; printf(输入顶点序列(以#结束)：n); while(v=getchar

13、()!=#) g-vexsi=v; /*读入顶点信息*/ i+; g-vexnum=i; for(i=0;i6;i+) /*邻接矩阵初始化*/ for(j=0;jarcsij=INF; printf(输入边的信息：n); scanf(%d,%d,%d,&i,&j,&w); /*读入边(i,j,w)*/ while(i!=-1) /*读入i为1时结束*/ g-arcsij=w; if(flag=1) g-arcsji=w; scanf(%d,%d,%d,&i,&j,&w); void prim(graph *g,int u)/*出发顶点u*/ int lowcostN,closestN,i,j,

14、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&lowcostjvexsclosestk,g-vexsk,lowcostk); /*输出该边*/ lowcostk=0; /*顶点k纳入最小生成树 */ for(j=0;jvexnum;j+) /*求其他顶点到顶点k 的权

15、*/ if(g-arcskj!=0&g-arcskjarcskj; closestj=k; void printPath(graph g,int startVex,int EndVex) int stackN,top=0; /*堆栈*/ int i,k,j; int flagN; /*输出路径顶点标志*/ k=EndVex; for (i=0;i0) /*找j到k的路径*/ for (i=0;i %c(%d) ,g.vexsi,g.arcsji); /*输出j到k的路径的顶点i*/ flagi=1; j=i; k=stack-top; break; else if (i!=k) stackto

16、p+=i; /*break;*/ void dijkstra(graph g,int v) /*dijkstra算法求单源最短路径*/ int pathNN,distN,sN; int mindis,i,j,u,k; for(i=0;ig.vexnum;i+) disti=g.arcsvi; si=0; for(j=0;jg.vexnum;j+) pathij=0; if(distiINF) pathiv=1; pathii=1; distv=0; sv=1; for(i=0,u=1;ig.vexnum;i+) mindis=INFIN; for(j=0;jg.vexnum;j+) if(sj

17、=0) if(distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.vexnum;j+) if(sj=0)&distu+g.arcsujdistj) distj=distu+g.arcsuj; for(k=0;k到各顶点的最短路径n,g.vexsv); for(i=0;i顶点%c：,g.vexsv,g.vexsi); if(disti=INF|disti=0) printf(无路径); else printf(%d ,disti); printf(经过顶点：); printPath(g,v,i); /*输出v到i的路径*/ void showprim

18、()/*最小生成树prim算法演示*/ graph ga; createGraph_w(&ga,1); prim(&ga,0);void showdij() /*dijstra算法演示*/ graph ga; createGraph_w(&ga,0); dijkstra(ga,0);int main()showprim(); /*prim算法演示*/getchar(); showdij(); /*dijstra算法演示*/ return 0; 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。最小生成树 最短路径ABCDEF#0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-1,-1,-1ABCDEF#0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-1,-1,-1 运行结果：（并画出两个图）最小生成树 最短路径四、实验小结图的表示和变厉需要很强的逻辑性 五、教师评语