北邮数据结构实验 第二次实验 图教学内容.doc

《北邮数据结构实验 第二次实验 图教学内容.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、…………………………………………………………最新精品资料推荐……………………………………………………数据结构实验报告1．实验要求（1）实验目的通过选择下面5个题目之一进行实现，掌握如下内容：Ø掌握图基本操作的实现方法Ø了解最小生成树的思想和相关概念Ø了解最短路径的思想和相关概念Ø学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小

2、生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2.程序分析2.1存储结构图：(1)带权值的无向图V096V12V2(2)带权值的有向图V0…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………6394V12V22.2关键算法分析（1）深度优先遍历intvisited[MAXSIZE]={false

3、};templatevoidMGraph::DFS(intv){cout<

4、=0;j…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐………

5、……………………………………………intmininum(MGraphG,inta[]){intmin=MAX;intk=0;for(inti=0;ivoidMGraph::Prim(MGraphG){for(inti=0;i

6、i];}lowcost[0]=0;//初始化U={vo}for(inti=1;iV"<

7、²)（4）克鲁斯卡尔算法templatevoidGenSortEdge(MGraphG,VEdgeE[])//获取EdgeList…………………………………………………………最新精品资料推荐……………………………………………………15…………………………………………………………最新精品资料推荐……………………………………………………{intk=0,i,j;for(i=0;i

8、E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=2