《数据结构图参考模板.doc》由会员分享，可在线阅读，更多相关《数据结构图参考模板.doc（17页珍藏版）》请在三一文库上搜索。
1、常熟理工学院数据结构与算法实验指导与报告书_2017-2018_学年 第_1_ 学期专 业： 物联网工程 实验名称： 实验七 图 实验地点： N6-210 指导教师： 聂盼红 计算机科学与工程学院20171 / 17实验七 图【实验目的】1、掌握图的邻接矩阵和邻接表表示。2、掌握图的深度优先和广度优先搜索方法。3、掌握图的最小生成树Prim算法。4、掌握图的拓扑排序算法。5、掌握图的单源最短路径dijkstra算法。【实验学时】4-6学时【实验预习】回答以下问题：1、写出图7-1无向图的邻接矩阵表示。2、写出图7-2有向图的邻接表表示。3、写出图7-1的深度优先搜索序列和广度优先搜索序列。深度
2、优先搜索序列：A,C,B,D,E,F,G,H广度优先搜索序列：A,B,C,D,E,F,G,H,4、写出图7-2的拓扑序列，说明该有向图是否有环？拓扑序列:EABCD该有向图没有环5、根据图7-3，写出其最小生成树。图7-3 无向带权图G36、根据图7-4，求从顶点A到其他顶点的单源最短路径。X图7-4有向带权图G4单源最短路径：=10:AC=50:AED=30:AE=60:AEDF【实验内容和要求】1、 编写程序exp7_1.c，实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索。以图7-1的无向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）exp7_1.c参考程序
3、如下：#include#define N 20#define TRUE 1#define FALSE 0#define MAX 100int visitedN;/*访问标志数组*/typedef struct /*辅助队列的定义*/ int dataN; int front,rear;queue;typedef struct /*图的邻接矩阵表示*/ int vexnum,arcnum; char vexsN; int arcsNN;MGraph;void createGraph(MGraph *g); /*建立一个无向图的邻接矩阵*/void dfs(int i, MGraph *g); /
4、*从第i个顶点出发深度优先搜索*/void tdfs(MGraph *g); /*深度优先搜索整个图*/void bfs(int k, MGraph *g); /*从第k个顶点广度优先搜索*/void tbfs(MGraph *g); /*广度优先搜索整个图*/void init_visit(); /*初始化访问标识数组*/void createGraph(MGraph *g) /*建立一个无向图的邻接矩阵*/ int i=0,j,e=0; char v; g-vexnum=0; g-arcnum=0; printf(n输入顶点序列(以#结束)：n); while (v=getchar()!=
5、#) g-vexsi=v; /*读入顶点信息*/ i+; g-vexnum=i; /*顶点数目*/ for (i=0;ivexnum;i+) /*邻接矩阵初始化*/ for (j=0;jvexnum;j+) g-arcsij=0;/*（1）-邻接矩阵元素初始化为0*/ printf(n输入边的信息(顶点序号,顶点序号)，以(-1,-1)结束：n); scanf(%d,%d,&i,&j); /*读入边(i,j)*/ while (i!=-1) /*读入i为1时结束*/ g-arcsij=1;/*（2）-i,j对应边等于1*/ e+; scanf(%d,%d,&i,&j); g-arcnum=e;
6、 /*边数目*/* createGraph */*（3）-从第i个顶点出发深度优先搜索，补充完整算法*/void dfs(int i, MGraph *g) int j; printf(%c,g-vexsi); visitedi=1; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) dfs(j,g);/* dfs */void tdfs(MGraph *g) /*深度优先搜索整个图*/ int i; printf(n从顶点%C开始深度优先搜索序列：,g-vexs0); for (i=0;ivexnum;i+) if (visitedi!=1) /*
7、（4）-对尚未访问过的顶点进行深度优先搜索*/ dfs(i,g); printf(n);/*tdfs*/void bfs(int k, MGraph *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)
8、%N; for (j=0;jvexnum;j+) if (g-arcsij=1)&(!visitedj) printf(%c,g-vexsj); visitedj=TRUE; q-dataq-rear=j; /*（5）-刚访问过的结点入队*/ q-rear=(q-rear+1)%MAX; /*（6）-修改队尾指针*/ /*bfs*/void tbfs(MGraph *g) /*广度优先搜索整个图*/ int i; printf(n从顶点%C开始广度优先搜索序列：,g-vexs0); for (i=0;ivexnum;i+) if (visitedi!=TRUE) bfs(i,g);/*从顶点i
9、开始广度优先搜索*/ printf(n);/*tbfs*/void init_visit() /*初始化访问标识数组*/ int i; for (i=0;iN;i+) visitedi=FALSE;int main() MGraph ga; int i,j; printf(*图邻接矩阵存储和图的遍历*n); printf(n1-输入图的基本信息：n); createGraph(&ga); printf(n2-无向图的邻接矩阵：n); for (i=0;iga.vexnum;i+) for (j=0;jga.vexnum;j+) printf(%3d,ga.arcsij); printf(n);
10、 printf(n3-图的遍历：n); init_visit(); /*初始化访问数组*/ tdfs(&ga); /*深度优先搜索图*/ init_visit(); tbfs(&ga); /*广度优先搜索图*/ return 0;2、 编写程序exp7_2.c，实现图的邻接表存储和拓扑排序算法。以图7-2的有向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）exp7_2.c程序代码参考如下：#include#include#define N 20/*图的邻接表：邻接链表结点*/typedef struct EdgeNode int adjvex; /*顶点序号*/ st
11、ruct EdgeNode *next; /*下一个结点的指针*/ EdgeNode;/*图的邻接表：邻接表*/typedef struct VNode char data; /*顶点信息*/ int ind; /*顶点入度*/ struct EdgeNode *link; /*指向邻接链表指针*/ VNode;typedef struct ALgraph /*图的邻接表*/ int vexnum,arcnum; /*顶点数、弧数*/ VNode adjlistN;ALGraph;void createGraph_list(ALGraph *g); /*建立有向图的邻接表*/void topS
12、ort(ALGraph *g); /*拓扑排序*/*建立有向图的邻接表*/void createGraph_list(ALGraph *g) int i,j,e; char v; EdgeNode *s; i=0; e=0; printf(n输入顶点序列(以#结束)：n); while(v=getchar()!=#) g-adjlisti.data=v; /*读入顶点信息*/ g-adjlisti.link=NULL; g-adjlisti.ind=0; i+; g-vexnum=i; /*建立邻接链表*/ printf(n请输入弧的信息(顶点序号,顶点序号)，以(-1,-1)结束:n); s
13、canf(%d,%d,&i,&j); while(i!=-1) s=(struct EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=j; s-next=g-adjlisti.link; ; /*（1）s插入链表*/ g-adjlisti.link=s; g-adjlistj.ind+; /*（2）顶点j的入度加1*/ e+; scanf(%d,%d,&i,&j); g-arcnum=e;/*createGraph_list*/void topSort(ALGraph *g) /*拓扑排序*/ int i,j,k,top=0,m=0,sN; /*m为拓扑排
14、序输出的结点数*/ EdgeNode *p; for(i=0; ivexnum; i+) if(!g-adjlisti.ind) /*（3）入度为0的顶点入栈*/ stop+=i; printf(n输出拓扑序列：); while(top0) j=s-top; printf(%c,g-adjlistj.data); m+; p=g-adjlistj.link; while(p!=NULL) k=p-adjvex; g-adjlistk.ind-; /*顶点k入度减1*/ if(g-adjlistk.ind=0) /*顶点k入度为0，进栈*/ stop+=k; p=p-next; printf(n
15、共输出%d个顶点n,m); if(mvexnum) /*（4）当输出顶点数小于图的顶点数，表示有环*/ printf(图中有环！); else printf(图中无环！);/*topSort*/int main() ALGraph g; int i; EdgeNode *s; printf(*图的邻接表存储结构和拓扑排序*n); printf(n1-输入图的基本信息：n); createGraph_list(&g); /*创建图的邻接表存储结构*/ printf(n2-图的邻接表:); for(i=0; i%d,s-adjvex); s=s-next; printf(n); printf(n3
16、-根据图的邻接表实现拓扑排序：n); topSort(&g); /*进行拓扑排序*/ return 0;（3）调试下面给出的图的信息，写出运行结果，画出该有向图。ABCDEF#1,01,32,12,53,23,43,54,05,05,15,4-1,-13、编写程序exp7_3.c，实现带权图的存储、图的最小生成树及单源最短路径算法。以图7-3（求该图最小生成树）和图7-4（求该图的单源最短路径）为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）exp7_3.c程序代码参考如下：#include #define N 20#define TRUE 1#define INF 10
17、002766 /*邻接矩阵中的无穷大元素*/#define INFIN 10002767 /*比无穷大元素大的数*/typedef struct/*图的邻接矩阵表示*/ int vexnum,arcnum; char vexsN; int arcsNN;MGraph;void printPath(MGraph g, int startVex, int EndVex, int pathN); /*打印最短路径*/void createMGraph_w(MGraph *g, int flag); /*建带权图的邻接矩阵*/void prim(MGraph *g, int u); /*求最小生成树P
18、rim算法，u为出发顶点*/void dijkstra(MGraph g, int v); /*dijkstra算法求单源最短路径*/void createMGraph_w(MGraph *g, int flag)/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/ int i,j,w; char v; g-vexnum=0; g-arcnum=0; i=0; printf(n输入顶点序列(以#结束)：n); while(v=getchar()!=#) g-vexsi=v; /*读入顶点信息*/ i+; g-vexnum=i; for(i=0; i6; i+) /*邻接矩
19、阵初始化*/ for(j=0; jarcsij=INF; printf(n输入边的信息：(顶点，顶点，权值)，以(-1,-1,-1)结束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); /*createMGraph_w*/void prim(MGraph *g, int u)/*求最小生成树Prim算法，u为出发顶点*/ int lowcostN,closestN,i,j,k,min
20、; for(i=0; ivexnum; i+) /*求其他顶点到出发顶点u的权*/ lowcosti=g-arcsuj;/*（1）-顶点i到u的代价最小的边权值*/ closesti=u; lowcostu=0; printf(n最小生成树：n); for(i=1; ivexnum; i+) /*循环求最小生成树中的各条边*/ min=INFIN; for(j=0; jvexnum; j+) /*选择得到一条代价最小的边*/ if(lowcostj!=0&lowcostjvexsclosestk,g-vexsk,lowcostk); /*输出该边*/ lowcostk=0; /*顶点k纳入最小
21、生成树 */ for(j=0; jvexnum; j+) /*求其他顶点到顶点k 的权*/ if(g-arcskj!=0&g-arcskjarcskj; /*（3）-其他顶点到k的代价最小的边权值*/ closestj=k; /*prim*/void printPath(MGraph g, int startVex, int EndVex, int pathN) 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.ar
22、csji); /输出j到k路径顶点i flagi=1; j=i; k=stack-top; break; else if (i!=k) stacktop+=i; if (flagk=0) printf(- %c(%d),g.vexsk,g.arcsjk);void dijkstra(MGraph g, int v)/*dijkstra算法求单源最短路径*/ int sN, pathNN,distN; 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
23、; 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=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.v
24、exsi); if (disti=INF|disti=0) printf(无路径); else printf(%d ,disti); printf(经过顶点：); printPath(g,v,i,path); /输出v到i的路径 /*dijkstra*/int main() int select; MGraph ga; do printf(n*MENU*n); printf( 1. 图的最小生成树-Prim算法n); printf( 2. 图的单源最短路径-dijstra算法n); printf( 0. EXIT); printf(n*MENU*n); printf(ninput choice
25、:); scanf(%d,&select); getchar(); switch(select) case 1: printf(n1-图的最小生成树-Prim算法n); printf(n输入带权图的基本信息：n); createMGraph_w(&ga,1); prim(&ga,0); break; case 2: printf(n2-图的单源最短路径-dijstra算法n); printf(n输入带权图的基本信息：n); createMGraph_w(&ga,0); dijkstra(ga,0); break; default: break; while(select); return 0;
26、【拓展实验】4、编写算法，实现最小生成树的Kruskal算法。提示：Kruskal算法实现的基本步骤：（1）需要对图中所有的边进行排序，因此需要借助一个辅助数组edge来存储按权值由小到大排序的边。包括边的权值、边的起点和终点。（2）每加入一条边，需要判断该边的两个顶点是否处在同一连通分量上，可以利用数组parents来表示各顶点的状况，parentsi=i；初始值设置为各自的顶点值，表示各顶点自成一连通分量。当加入该边，需要对该边的边头顶点和边尾顶点的parents值相等。5、编写算法，实现图的最短路径Floyd算法。提示：弗洛伊德算法的基本步骤：对有向图采用带权邻接矩阵存储，同时定义一个二
27、维数组ANN存放顶点i到j的最短路径。（1）初始化Aij=arcsij;（2）考虑vi和vj之间的路径，是否存在途经vk的路径（vi,vk,vj),若存在，比较Aik+AKj和Aij的距离，较小送Aij； 重复上步，取vk为图中所有顶点，直到比较完毕。同时还必须定义一个矩阵记录最短路径经过的顶点。void Floyd()Int i,j,k; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;jDi,k+Dk,j) Di,j=Di,k+Dk,j;6、编写算法，实现图的关键路径算法。提示：基于邻接矩阵的关键路径的求解步骤：(1)对AOE网进行拓扑排序，同时按拓扑序列的次序求出各顶点事件的最早发生时间ve，若网中存在回路，则算法终止，否则执行步骤(2)；(2)按拓扑序列的逆序求出各顶点事件的最迟发生时间vl；(3)根据各顶点事件的ve和vl值，求出各顶点活动ai的最早发生时间e(i)和最迟发生时间l(i)。若e(i)l(i)，则ai为关键活动。【实验小结】通过实验七图，我学会了的邻接矩阵和邻接表表示,学会了图的深度优先和广度优先搜索方法以及图的最小生成树Prim算法、图的拓扑排序算法。