1、Visual C+ 6.0 调试功能 图解教程 (4)-实例三 图 1. 实验目的 熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深 度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。 关于各种典型著名的复杂算法，在上机实习方面不做基本要求。更适合于安排大型课 程设计。 二 .需求分析 本程序演示用 C+编写 ,完成有向图的创建 ,用 Prim算法实现最小生成树 ,实现边的插入和删除 . 输入值的范围 :创建图时要求输入的结点个数不大于 MaxVertices 的值 .在插 入边时要求原图不存在起点和终点之间边 ,并且插入的边不是矩阵对角线上的边 .输入的数据类
2、型为整形 . 输出形式 :以邻接矩阵的形式输出图的数据项 .如果操作非法则给出错误信息 . 测试数据 A 创建 5 个顶点 4 条边的图 :输入顶点分别为 1,2,3,4,5;1 和 2 之间 ,2 和 3 之间 ,3 和 4 之间 ,4 和 5 之间的权值分别为 10,20,30,40.得到图 : 输出顶点的信息（整型）： 1 2 3 4 5 输出邻接矩阵 ： 1: 0 10 1000 1000 1000 2: 1000 0 20 1000 1000 3: 1000 1000 0 30 1000 4: 1000 1000 1000 0 40 5: 1000 1000 1000 1000 0
3、B 顶点 4 和 3 之间插入一条权值为 50 边得 输出顶点的信息（整型）： 1 2 3 4 5 输出邻接矩阵 ： 1: 0 10 1000 1000 1000 2: 1000 0 20 1000 1000 3: 1000 1000 0 30 1000 4: 1000 1000 50 0 40 5: 1000 1000 1000 1000 0 C 删除顶点 4 和 3 之间的边得 输出顶点的信息（整型）： 1 2 3 4 5 输出邻接矩阵 ： 1: 0 10 1000 1000 1000 2: 1000 0 20 1000 1000 3: 1000 1000 0 30 1000 4: 100
4、0 1000 1000 0 40 5: 1000 1000 1000 1000 0 三 .设计概要 (1)为了实现上述程序的功能 ,需要定义图的抽象数据类型 : ADT Graph is 数据对象： D=ai|ai IntegerSet,i=0,1,2,n,n0 基本操作 : CreatG() 操作结果 :创建有向图 InsertE() 初始条件 :有向图已经存在 操作结果 :插入一条边 DeleteE () 初始条件 : 有向图已经存在 操作结果 :删除一条边 END ADT BiTree (2) 本程序包含一个类和一个结构体类型 A 无向图类 AdjMWGraph 有 7 个函数 1 主函
5、数 main() 2.构造函数 AdjMWGraph() 3. 创建图函数 CreatG(int n,int e) 4. 插入边函数 InsertE() 5. 删除边函数 DeleteE() 6. 求最小生成树 Prim 算法函数 Prim() B 结构体类型 MinSpanTree (3)本程序的两个文件 1.头文件 Graph.h 2.源文件 Graph.cpp (4)函数之间的关系 四 .详细设计 1 /Graph.h 2 #include “iostream“ 3 #include 4 #include 5 using namespace std; 6 const int MaxVer
6、tices=10; 7 const int MaxWeight=1000; 8 struct MinSpanTree /带权边的三个参数 9 10 int begin,end; /边的起点与终点 11 int length; /边的权值 12 ; 13 14 class AdjMWGraph 15 16 private: 17 int Vertices20; /顶点信息的数组 18 int EdgeMaxVerticesMaxVertices; /边的权信息的矩阵 19 int numE; /当前的边数 20 int numV; /当前的顶点数 21 public: 22 AdjMWGraph
7、(); /构造函数 23 void CreatG(int n,int e); /创建图函数 24 void PrintOut(); /打印图中数据项函数 25 void Prim() ; /求最小生成树方法 (Prim算法 ) 26 void InsertE(); /插入边函数 27 void DeleteE(); /删除边函数 28 ; 29 /Graph.cpp 30 #include “Graph.h“ 31 32 /初始化矩阵 33 AdjMWGraph:AdjMWGraph() /构造函数 34 35 /初始化矩阵为 36 for ( int i = 0; i Verticesi;
8、61 62 63 64 /边赋权值 65 for ( int i = 0; i vi vj w; 69 70 /判断起点和终点是否存在 ,是否是对角线上的点并且边是否存在 71 if (vi != vj ) 72 154 /判断起点各终点是否存在并且不是对角线上的点 155 if ( ( i != j ) 181 if (i0 219 220 switch(k) 221 222 223 case 1: 224 225 cout n e ; 227 G.CreatG(n,e); 228 G.PrintOut(); 229 cout 0 253 return 0; 254 255 五 .心得 :
9、这次实验我把无向图改成有向图后 ,对实验中给出的生成最小生成树的 Prim 算法感到费解这里只能说说在实现插入和删除时的心得 .在创建图时我在程序中加入判断语句 ,因 为在给边权时如果顶点不存在会造成锁死 ,严重影响调试 .在创建和插入中主要判断的是 :1,顶点是否越界 .2 边是否已经存在 .3 插入位置是否是矩阵的对角线 .在删除中判断 1,顶点是否越界 .2 边是否已经存在 .对于 Prim 算法的求最小生成树的思想能够理解 ,但对于算法的实现不甚理解 .希望老师在下次实验时讲解 . 六 .使用说明 程序名为 No5.exe 运行环境为 DOS,执行后显示 : 在 “ 请输入您的选择 (1,2,3,4):“后输入数字选择执行的功能 . 测试结果 : 1. 选择 1.输入如图 :
