数据结构上机实践6.doc

数据结构上机实践6实践目的掌握图的存储结构；掌握有关图的操作算法并能用C语言实现。预备知识1图的邻接表存储结构描述如下： #define VEX_NUM 10 /*顶点数目*/ typedef char Vextype; /*顶点类型*/ typedef struct arcnode int adjvex; struct arcnode *nextarc; ArcNode; /*表结点*/ typedef struct vnode Vextype data; ArcNode *firstarc; VNode; /* 头结点*/ typedef VNode ALgraphVEX_NUM; /*图的邻接链表*/ 2基本算法（1）图的建立算法void creat_Mgraph( Mgraph *G,int e) /*建立无向图的邻接矩阵G ，e为边的数目*/ for (i=0;ivexsi); /*输入顶点信息*/ for (i=0;iVEX_NUM;+i) for (j=0;jarcsij=0; for(k=0;karcsij=1;G-arcsji=1; /* creat_Mgraph */（2）图的遍历int visitedNAX_VEX=0; void Dfs_m( Mgraph *G,int i) /* 从第i个顶点出发深度优先遍历图G，G以邻接矩阵表示*/ printf(%3c,G-vexsi); /*访问顶点vi*/ visitedi=1; for (j=0;jarcsij=1)& (!visitedj) Dfs_m(G,j); /*Dfs_m */应用范例从某源点到其余顶点之间的最短路径#define VEX_NUM 6#define MAXINT 1000#include typedef char Vextype;typedef struct Vextype vexsVEX_NUM; int arcsVEX_NUMVEX_NUM; Mgraph; void creat_Mgraph( Mgraph *G,int e) int i,j,w,k; for (i=0;iVEX_NUM;+i) for (j=0;jarcsij=0; else G-arcsij=MAXINT; printf(输入:n ); for(k=0;karcsij=w; /* creat_Mgraph */ void Dijkstra(Mgraph Gn, int v0,int path,int dist) int i,j,v,w,min; int sVEX_NUM; for(v=0; vVEX_NUM; v+) sv=0; distv=Gn.arcsv0v; if(distvMAXINT) pathv=v0; else pathv=-1; distv0=0;sv0=1; for(i=1;iVEX_NUM -1;i+) min=MAXINT; for(w=0;wVEX_NUM;w+) if(!sw & distwmin) v=w;min=distw; sv=1; for(j=0;jVEX_NUM;j+) if(!sj & (min+Gn.arcsvjdistj) distj=min+Gn.arcsvj; pathj=v; /*if*/ /*for*/ /*Dijkstra*/ void Putpath(int v0,int p,int d) /*输出源点v0到其余顶点的最短路径和路径长度*/ int i,next; for(i=0;iVEX_NUM;i+) if(diMAXINT & i!=v0) printf(v%d-,i); next=pi; while(next!=v0) printf(v%d-,next); next=pnext; printf(v%d:%dn,v0,di); else if(i!=v0) printf(v%d-v%d:no pathn,i,v0); /*Putpath*/main()Mgraph G;int e,v0;int pathVEX_NUM,distVEX_NUM;printf(输入有向网的弧数:);scanf(%d,&e);creat_Mgraph(&G,e);printf(输入有向网的源点:);scanf(%d,&v0);Dijkstra(G, v0, path, dist);printf(nv%d到其余顶点的最短路径:n,v0);Putpath(v0,path,dist);getch(); 以教材P.86 图5-5-1所示有向网为例