数据结构上机实践6

《数据结构上机实践6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构上机实践6实践目的掌握图的存储结构；掌握有关图的操作算法并能用C语言实现。预备知识1．图的邻接表存储结构描述如下：#defineVEX_NUM10/*顶点数目*/typedefcharVextype;/*顶点类型*/typedefstructarcnode{intadjvex;structarcnode*nextarc;}ArcNode;/*表结点*/typedefstructvnode{Vextypedata;ArcNode*firstarc;}VNode;/*头结点*/typedefVNodeALgraph[VEX_NUM];/*

2、图的邻接链表*/2．基本算法（1）图的建立算法voidcreat_Mgraph(Mgraph*G,inte){/*建立无向图的邻接矩阵G，e为边的数目*/for(i=0;ivexs[i]);/*输入顶点信息*/for(i=0;iarcs[i][j]=0;for(k=0;karcs[i][j]=1;G->

3、arcs[j][i]=1;}}/*creat_Mgraph*/（2）图的遍历intvisited[NAX_VEX]={0};voidDfs_m(Mgraph*G,inti){/*从第i个顶点出发深度优先遍历图G，G以邻接矩阵表示*/printf("%3c",G->vexs[i]);/*访问顶点vi*/visited[i]=1;for(j=0;jarcs[i][j]==1)&&(!visited[j]))Dfs_m(G,j);}/*Dfs_m*/4应用范例——从某源点到其余顶点之间的最短路径#define

4、VEX_NUM6#defineMAXINT1000#includetypedefcharVextype;typedefstruct{Vextypevexs[VEX_NUM];intarcs[VEX_NUM][VEX_NUM];}Mgraph;voidcreat_Mgraph(Mgraph*G,inte){inti,j,w,k;for(i=0;iarcs[i][j]=0;elseG->arcs[i][j]=MAXINT;printf("

5、输入:");for(k=0;karcs[i][j]=w;}}/*creat_Mgraph*/voidDijkstra(MgraphGn,intv0,intpath[],intdist[]){inti,j,v,w,min;ints[VEX_NUM];for(v=0;v

6、t[v0]=0;s[v0]=1;for(i=1;i

7、td[]){/*输出源点v0到其余顶点的最短路径和路径长度*/inti,next;for(i=0;i

8、v0;intpath[VEX_NUM],dist[VEX_NUM];printf("输入有向网的弧数:");scanf("%d",&e);creat_Mgraph(