《2012《数据结构》上机指导(3)-图》由会员分享，可在线阅读，更多相关《2012《数据结构》上机指导(3)-图（3页珍藏版）》请在金锄头文库上搜索。
1、1实验实验 3 图图一、实验目的一、实验目的1熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历 和广度优先遍历。进一步掌握递归算法的设计方法。 2关于各种典型著名的复杂算法，在上机实验方面不做基本要求。更适合于安排大型课程设计。二、实例二、实例网的邻接矩阵存储（数组表示） 、简单输出，最小生成树。 本实例的目的是给出一个网的数组表示的简单启示，并采用 Prim 算法实现最小生成树的操作。对于 图的两种遍历方法教材上已很全面。在下面的程序中，只给出图的建立、输出及最小生成树的 Prim 算法。#include #include const int MaxVer
2、tices=10; const int MaxWeight=10000; struct MinSpanTree /带权边的三个参数 int begin,end; /边的起点与终点int length; /边的权值 ; class AdjMWGraph private:int Vertices10; /顶点信息的数组int EdgeMaxVerticesMaxVertices; /边的权信息的矩阵int numE; /当前的边数 int numV; /当前的顶点数 public: AdjMWGraph(); /构造函数void CreatG(int n,int e);void PrintOut(
3、);void Prim() ;/求最小生成树方法 ; AdjMWGraph:AdjMWGraph() /构造函数 for ( int i=0; iVerticesi;for (i=0; ivivjw;Edgevi-1vj-1=w; Edgevj-1vi-1=w; /对于无向图 void AdjMWGraph:PrintOut() int i;coutn ;coute ;G.CreatG(n,e); G.PrintOut();cout“最小生成树如下“;cout“（共有“n-1“条边）：n“ ;G.Prim(); return 0; 三、实验题目三、实验题目1. 设计一个程序，建立有向图的邻接矩阵，进行深度优先遍历， （选做）并利用广度优先遍历算法判 断有向图中是否存在顶点 vi到顶点 vj的路径（ij，顶点 vi和顶点 vj由键盘输入指定） 。 2. 设计一个程序，建立无向图的邻接链表，进行广度优先遍历， （选做）并利用深度优先遍历算法判 断无向图中是否存在顶点 vi到顶点 vj的路径（ij，顶点 vi和顶点 vj由键盘输入指定） 。
