《(完整word版)数据结构--图.doc》由会员分享，可在线阅读，更多相关《(完整word版)数据结构--图.doc（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实验指导V2017常熟理工学院数据结构与算法实验指导与报告书_2017-2018_学年 第_1_ 学期专 业： 物联网工程 实验名称： 实验七 图 实验地点： N6-210 指导教师： 聂盼红 计算机科学与工程学院2017实验七 图【实验目的】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的无向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）ex
3、p7_1.c参考程序如下：#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, MGr
4、aph *g); /*从第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=g
5、etchar()!=#) 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
6、-arcnum=e; /*边数目*/* 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 (visit
7、edi!=1) /*（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=(
8、q-front+1)%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
9、,g);/*从顶点i开始广度优先搜索*/ 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);
10、printf(n); 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; /
11、*顶点序号*/ struct 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 topSort(ALGraph *g); /*拓扑排序*/*建立有向图的邻接表*/void createGraph_list(ALGraph *g) int i,j,e; char v; EdgeNode *s; i=0; e=0; printf(n输入顶点序列(以#
