(完整word版)数据结构--图.doc

《数据结构与算法》实验指导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的深度优先搜索序列和广度优先搜索序列深度优先搜索序列：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参考程序如下：#include#define N 20#define TRUE 1#define FALSE 0#define MAX 100int visited[N]; /*访问标志数组*/typedef struct { /*辅助队列的定义*/ int data[N]; int front,rear;}queue;typedef struct { /*图的邻接矩阵表示*/ int vexnum,arcnum; char vexs[N]; int arcs[N][N];}MGraph;void createGraph(MGraph *g); /*建立一个无向图的邻接矩阵*/void dfs(int i, MGraph *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=getchar())!='#') { g->vexs[i]=v; /*读入顶点信息*/ i++; } g->vexnum=i; /*顶点数目*/ for (i=0;ivexnum;i++) /*邻接矩阵初始化*/ for (j=0;jvexnum;j++) g->arcs[i][j]=0;/*（1）-邻接矩阵元素初始化为0*/ printf("\n输入边的信息(顶点序号,顶点序号)，以(-1,-1)结束：\n"); scanf("%d,%d",&i,&j); /*读入边(i,j)*/ while (i!=-1) { /*读入i为－1时结束*/ g->arcs[i][j]=1;/*（2）-i,j对应边等于1*/ e++; scanf("%d,%d",&i,&j); } g->arcnum=e; /*边数目*/}/* createGraph *//*（3）---从第i个顶点出发深度优先搜索，补充完整算法*/void dfs(int i, MGraph *g){ int j; printf("%c",g->vexs[i]); visited[i]=1; for(j=0;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j])) dfs(j,g);}/* dfs */void tdfs(MGraph *g) { /*深度优先搜索整个图*/ int i; printf("\n从顶点%C开始深度优先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i]!=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->vexs[k]); visited[k]=TRUE; q->data[q->rear]=k; q->rear=(q->rear+1)%N; while (q->rear!=q->front) { /*当队列不为空，进行搜索*/ i=q->data[q->front]; q->front=(q->front+1)%N; for (j=0;jvexnum;j++) if ((g->arcs[i][j]==1)&&(!visited[j])) { printf("%c",g->vexs[j]); visited[j]=TRUE; q->data[q->rear]=j; /*（5）---刚访问过的结点入队*/ q->rear=(q->rear+1)%MAX; /*（6）---修改队尾指针*/ } }}/*bfs*/void tbfs(MGraph *g) { /*广度优先搜索整个图*/ int i; printf("\n从顶点%C开始广度优先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i]!=TRUE) bfs(i,g); /*从顶点i开始广度优先搜索*/ printf("\n");}/*tbfs*/void init_visit(){ /*初始化访问标识数组*/ int i; for (i=0;i

以图7-2的有向图为例，补充完整程序，调试运行并写出运行结果运行结果：（包括输入数据）exp7_2.c程序代码参考如下：#include#include#define N 20/*图的邻接表：邻接链表结点*/typedef struct EdgeNode{ int adjvex; /*顶点序号*/ struct EdgeNode *next; /*下一个结点的指针*/} EdgeNode;/*图的邻接表：邻接表*/typedef struct VNode{ char data; /*顶点信息*/ int ind; /*顶点入度*/ struct EdgeNode *link; /*指向邻接链表指针*/} VNode;typedef struct ALgraph{ /*图的邻接表*/ int vexnum,arcnum; /*顶点数、弧数*/ VNode adjlist[N];}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输入顶点序列(以#。