一、课程设计题目与要求

【基本要求】

• 1）基于图一构造图（权值可以自行设计添加）；
• 2）分别使用深度优先遍历(DFS)、Prim、Dijkstra算法从任意用户输入的顶点开始对图进行遍历、求MST（最小生成树）及最短路径；
• 3）三个算法同时动态显示构造过程；
• 4）每一步都要求显示/打印所有试探的路径(见图二）；

【扩展要求】

• 1）务必掌握单步调试；
• 2）鼓励使用MFC或QT进行可视化；
• 3）使用命令行程序时可考虑使用清屏(命令cls)后重新绘图进行动画演示；

二、需求分析

图是一种常见的结构，应用非常广泛，对其操作也多种多样，其中最常用的三类操作分别为遍历、求最小生成树、求两点之间最短路径 。本程序分别用DFS、Prim、Dijkstra三种算法实现上述功能。

• DFS是深度优先搜索，特征是沿着一条路径走到头，然后再回溯。
• Prim算法是在不断的把节点加入最小生成树的过程中 添加边，从而生成最小生成树
• Dijkstra算法是不断的求起点到每个顶点的最短路径。

三、设计

3.1 设计思想

（1）数据结构设计

本程序主要采用邻接矩阵作为图的存储结构。算法中的顶点集合用数组存储。

（2）算法设计

三种算法：

DFS:

设置Visited[]保存是否被标记，stack s 用来保存遍历的序列
算法主体为：

• 1.当前位置Loc进栈，输出栈顶，标记Loc位置
• 2.找到与当前位置有连接的j，且j位置未标记，递归，把j作为Loc传给下一次的操作，直到所有节点均被访问为止

Prim:

设置Visited[]保存是否被标记，x[i][j]保存最短路径上的边，x[i][j]==1 表示边（i，j）在最短路径上。
算法主体为：

• 找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 ，符合条件的 i只有一个而j可以不止一个，
• 找到path[i][j]的权值最小的一个，visited[j]即对j位置访问，x[i][j]=1 即把边（i，j）纳入到最短路径中。
• 重复以上步骤直到Visited[]的值全为1为止。

Dijkstra:

设置Visited[]保存是否被标记，Dis[]保存用户起点到下标号的节点路径的长度，Father[]保存最短路径上的前一个节点。
算法主体有三步：

• 1更新：找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 且ij有连接，把(0,i)+（i，j）和(0,j)中的较小者赋给j，并且Father[j] = i即i作为j的前驱节点。
• 2访问：每轮在更新Dis后 判断最小未被标记的顶点 对其访问（vis = 1;）
• 重复1、2 步骤直到Visited[]的值全为1为止。

3.2 详细设计

“无向图”CC_Group类的构建：

数据成员有：

int C_Adj[MaxSize][MaxSize];
int C_Visited[MaxSize];
int C_PointNum;//顶点数
int C_ArcNum;//边数
C_Adj数组用来存储边的信息，C_Adj[i][j]不为零表示存在边（i，j）且这条边上的权值为C_Adj[i][j]的值。
C_Visited[i]用来存储节点是否被访问标记，为0则未标记，为1则已经被标记。默认全部为零。
C_Point表示当前图中的节点数
C_ArcNum表示当前图中的边数

函数成员有：

CC_Graph(int* PointNum, int* arcNum, int* C_Loc);
void DFS(stack s, int Loc);//深度优先遍历

构造函数的三个参数分别表示：点的数量，边的数量，程序开始的节点位置，在构造函数中会提示输入各种信息以完成对图的创建。

DFS即深度优先遍历，需要的参数是一个int类型的空栈和程序开始位置，采用递归的方法完成对图的深度优先遍历输出。

最小生成树Prim算法的实现：

在函数中定义Vis[i]保存i号节点是否被标记，x[i][j]保存最短路径上的边，x[i][j]不等1表示边（i，j）在最短路径上，数值表示被标记的次序，初始化均为0。vis[Loc] 赋值为1；定义Order来表示访问次序，isALL作为主循环的循环条件，在所有节点均被访问后被赋值为1，否则为0.

在主循环中实现以下算法：找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 ，符合条件的 i只有一个而j可以不止一个，找到path[i][j]的权值最小的一个，visited[j]即对j位置访问，x[i][j]=Order 即把边（i，j）纳入到最短路径中，并确定其被标记的次序，然后Order加一。

输出最小生成树有两种方法：

• 1.调用CoutMat(x, n)即自定义的用来输出二维数组的算法，更加直观的表示出哪些边在最小生成树中，以及其在其中的次序。
• 2.输出语句，首先定义tim=0；第一重循环判断条件tim不等于Order，再来两层循环对x数组做遍历，判断如果[i][j] == tim就输出（j，i）并且 tim++;

最短路径Dijkstra算法的实现：

设置Visited[]保存是否被标记，Dis[]保存用户起点到下标号的节点路径的长度，Father[]保存最短路径上的前一个节点。其他类似于Prim算法。
算法主体有三步：
1.更新：找到这样的两个顶点 即 i位置已经被访问 且j位置未被访问 且ij有连接，把(0,i)+（i，j）和(0,j)中的较小者赋给j，并且Father[j] = i即i作为j的前驱节点。 2.访问：每轮在更新Dis后 判断最小未被标记的顶点 对其访问（vis = 1;）
3.重复1、2 步骤直到Visited[]的值全为1为止。

然后是输出语句：
1.输出用户输入位置到其他各个顶点的最短路径长度：
直接一个循环输出Dis数组的前n位即可
2.输出用户输入位置到其他各个顶点的最短路径对应的路线：
首先设置i从0到n的循环每次都将i赋值给VVV作为终点，v是用户输入的起点位置。

while (Father[vvv] != -1 && Father[vvv] != v){cout << Father[vvv] << "<--";vvv = Father[vvv];}

根据Father数组内存的节点的前驱关系输出路线。

五、用户手册：

打开程序后自动提示输入图的顶点数和边数，输入后敲回车会再次提醒输入边的信息（格式为：端点 端点 权值）一组数据内部用空格分隔开，组与组之间用回车区分，代码最后给出了几组测试数据可以直接用于测试。 信息输入完成后，程序会再次提醒输入算法开始的位置，位置应该小于顶点数减一，正确输入后系统直接清屏后显示计算结果.
最先输出的是图的邻接矩阵表示，然后就是深度优先遍历的结果，格式为（点->边->点->）,然后是Prim算法输出的最小生成树，依次输出的是最小生成树上的几个边。最后是Dijkstra输出最短路径，首先输出的是指定起点到各顶点的最短路径长度，然后输出每个最短路径对应的路线。

六、测试数据及测试结果：