《实验7图的表示与遍历》由会员分享，可在线阅读，更多相关《实验7图的表示与遍历（14页珍藏版）》请在金锄头文库上搜索。
1、1 实验五图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验预习说明以下概念1、深度优先搜索遍历：从根开始一个一个搜索2、广度优先搜索遍历：从根的邻接点出发依次访问3、拓扑排序：一个无指向的点开始排序4、最小生成树：最小权的生成树5、最短路径：路径权数最小三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include #define N 20 #define TRUE 1 #define FALSE 0 int visitedN; typedef struct /*队列的定义 */ int dataN;
2、 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 个顶点出发深度优先搜索*/ 2 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; prin
4、tf(“输入边的信息：n“); scanf(“%d,%d“, /*读入边 i,j*/ while(i!=-1) /*读入 i,j为 1 时结束 */ g-arcsij=1; g-arcsji=1; scanf(“%d,%d“, void dfs(int i,graph *g) /*从第 i 个顶点出发深度优先搜索*/ int j; printf(“%c“,g-vexsi); visitedi=TRUE; for(j=0;jvexnum;j+) if(g-arcsij=1) void tdfs(graph *g) /*深度优先搜索整个图*/ int i; 3 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= 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)%N; f
6、or(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) bfs(i,g); void init_visit()/*初始化访问标识数组*/ int i; 4 for(i=0;i #include #define N 20 typedef struct
7、 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)； /*建立有向图的邻接表*/ void topSort(vnode g,int n)；
8、 /*拓扑排序 */ void createGraph_list(vnode adjlist,int *p) /*建立有向图的邻接表*/ int i,j,n,e; char v; 6 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请输入弧的信息(i=-1结束 ) ： i,j:n“); s
9、canf(“%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; void topSort(vnode g,int n) /*拓扑排序 */ 7 int main() vnode adjlistN; int n,*p;
10、p= createGraph_list(adjlist,p); return 0; 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入: ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1 运行结果：3、阅读并运行下面程序。#include 8 #define N 20 #define TRUE 1 #define INF 32766 /*邻接矩阵中的无穷大元素*/ #define INFIN 32767 /*比无穷大元素大的数*/ typedef struct /*图的邻接矩阵*/ int vexnum,arcnum; char vexsN; int arcsNN; gr
11、aph; 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“); whi
12、le(v=getchar()!=#) g-vexsi=v; /*读入顶点信息*/ i+; g-vexnum=i; for(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; 9 scanf(“%d,%d,%d“, void prim(graph *g,int u)/*出发顶点u*/ int lowcostN,closestN,i,j,k,min; for(i=0;ivexnu
13、m;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!=0 closestj=k; void printPath(graph g,i
14、nt 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) stacktop+=i; /*break;*/ 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); if(disti=INF|disti=0) printf(“无路径 “); else printf(“%d “,disti); printf(“经过顶点： “); printPath(g,v,i); /*输出 v 到 i 的路径 */ void
