一、 实验目的

  1. 掌握图的逻辑结构与存储结构；

  2. 掌握图的基本操作与最小生成树算法；

  3. 掌握利用C/C++编程语言实现数据结构的编程方法；

  4. 通过上机实践加强利用数据结构解决实际应用问题的能力；

二、 实验相关知识

  1. 图的邻接矩阵存储结构；

  2. 图的深度优先遍历算法，与连通性的判定；

  3. 图的最小生成树的Prim算法；

  4. 使用EasyX做简单的图形处理。

三、 实验内容与要求

利用EasyX实现在窗体中，通过鼠标交互方式，在窗体中绘制图的顶点，并通过鼠标选择边的端点，再利用输入框输入无向边的权重值，从而创建出图，并利用图的邻接矩阵的存储结构存储图信息。创建图后，利用深度优先遍历方法，遍历图中的各节点，若为连通图，则利用Prim算法求图的最小生成树。参考效果如下：

（1）点击鼠标在窗体中创建图的节点（按回车或节点个数等于节点的最大值结束）(已提供）

（2）鼠标选中无向边的两个端点，并利用输入框输入无向边的权重值（权重值为小于10000的整数），两顶点之间若不存在边，则边的权重值，设为无穷（一个大于10000的整数即可）（第一次实验任务点）

（3）从1号节点开始，进行深度优先遍历连通分支，若能遍历所有点，则判定为连通图，可以求最小生成树。（第二次实验任务点）

（4）利用Prim算法从1号节点开始，求图的最小生成树。（第二次实验任务点）

四、讲解视频

五、进一步思考

1、如何避免节点的重叠；

2、如何通过鼠标拖拉节点，调整图的绘图形状；

3、在求最小生成树过程中，可否显示closest数组和lowcost数组值的变化情况；

4、如何利用Dijkstra算法求单源点的最短路径。