北邮数据结构实验-第二次实验-图.doc

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

1、数据结构实验报告1．实验要求（1）实验目的通过选择下面5个题目之一进行实现，掌握如下内容：Ø掌握图基本操作的实现方法Ø了解最小生成树的思想和相关概念Ø了解最短路径的思想和相关概念Ø学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2.程序分析2.1存储结构图：(1)带权值的无向图V096V

2、12V2(2)带权值的有向图V06394V12V22.2关键算法分析（1）深度优先遍历intvisited[MAXSIZE]={false};templatevoidMGraph::DFS(intv){cout<

3、ile(f!=r){v=queue[++f];for(intj=0;jintmininum(MGraphG,inta[]){intmin=MAX;intk=0;for(inti=0;i

4、n)//寻找U-{V-U}中边权值最小的顶点{min=a[i];k=i;}}returnk;}templatevoidMGraph::Prim(MGraphG){for(inti=0;iV"<

5、ntj=0;jvoidGenSortEdge(MGraphG,VEdgeE[])//获取EdgeList{intk=0,i,j;for(i=0;i

6、].weight=G.arcs[i][j];k++;}for(i=0;iE[j].weight){VEdget=E[i];E[i]=E[j];E[j]=t;}}}constintMAX_VERTEXT=20;templatevoidMGraph::Kruskal(VEdgeE[],intn,inte){intvset[MAX_VERTEXT];for(inti=0;i

7、V"<