图及其应用(实验六)

《图及其应用(实验六)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验六图及其应用1•目的要求：（1）通过完成本实验，掌握图的两种基本的存储结构（邻接矩阵、邻接表），以及图的基本算法实现（建立、遍历），并能运用图结构分析解决一些实际问题。（2）木实验训练的要点是：图的两种基木存储结构，及各种操作的算法实现（建立、遍历、图的典型应用）。2.实验内容：（1）建立无向图和有向图的邻接矩阵存储，计算顶点的度，并输岀图的基木信息。（2）建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后输出图的基本信息。（3）编写完整的程序实现AOV网的拓扑排序。（4）编程求AOE网的关键路径。（5）编程实现单源点最短路径的Dijkstra算法。

2、三.实验主耍流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）建立无向图和冇向图的邻接矩阵存储，计算顶点的度，并输出图的棊本信息。>程序代码：头文件：#include#include#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefintStatus;#define1N1FIN1TY1000#defineMAX_VERTEX_NUM20typedefenum{DG,DN,UDG,UDN}GraphKind;typed

3、efcharVertexType;typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];〃顶点向量intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃邻接矩阵intvexnum,arcnum;〃顶点数和弧的数目〃图的种类GraphKindkind;}MGraph;intLovateVex(MGraphG,VertexTypev);StatusCreateUDN(MGraph&G);StatusCreateDN(MGraph&G);StatusCreateUDG(MGraph&G);StatusCreat

4、eDG(MGraph&G);StatusCreateGraph(MGraph&G);voidPrintGraph(MGraphG);voidGraphDegree(MGraphG);主函数：#includeMl.h"intmain(){MGraphG;CreateGraph(G);〃创建图PrintGraph(G);〃输'H图GraphDegree(G);〃计算图中顶点的度，并输出printf(uM);return0;}功能函数：intLovateVex(MGraphG,VertexTypev){for(inti=0;G.vexs[i]!=v;i++);retur

5、ni;}StatusCreateUDN(MGraph&G){inti,j,k;VertexTypevl，v2;intw;printfC*输入图的顶点数和边数：“);scanf(“％d%d^,&G.vexnum,&G.arcnum);printfC输入图的顶点信息：iT);for(i=O;i

6、k

7、num;i++)scanf("%c”,&G.vexs[i]);for(i=O;i