【Dev

目 录

• 需求分析                                                                                                                        1
• 概要设计                                                                                                                        2
• 详细设计                                                                                                                        3
• 调试分析                                                                                                                        9
• 运行结果                                                                                                                       11
• 参考文献                                                                                                                       12
• 附录                                                                                                                              13

一、需求分析

（1）输入的形式和输入值的范围；

首先构建带权的有向图，输入整数的顶点和边数。即城市的个数，航班路线的条数。再输入图的顶点元素，即城市的名称空格分开（例如：海口 昆明 南京 成都 西安 郑州 北京 哈尔滨）。最后通过输入航班路线（例如：海口 昆明 520 海口 南京 780 海口 成都 660 海口 郑州 830 昆明 成都 380 成都 西安 460 西安 郑州 220 西安 北京 680 南京 郑州 550 南京 北京 630 郑州 北京 400 北京 哈尔滨 860）。

（2）输出的形式；

输出按照图的深度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。

输出按照图的广度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。

输出最小代价完成这趟旅行的城市序列以及机票开销。

（3）程序所能达到的功能；

程序能通过航班路线以及票价的输入，能够输出按照图的深度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。输出按照图的广度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。输出最小代价完成这趟旅行的城市序列以及机票开销。

（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果：

正确的输入及其输出结果：顶点数、边数、边的信息和权值。输出按照图的深度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销，按照图的广度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销，以及最小代价完成这趟旅行的城市序列以及机票开销。

（例如：输入8 12  海口 昆明 南京  成都 西安 郑州 北京 哈尔滨 海口 昆明 520 海口 南京 780 海口 成都 660 海口 郑州 830 昆明 成都 380 成都 西安 460 西安 郑州 220 西安 北京 680 南京 郑州 550 南京 北京 630 郑州 北京 400 北京 哈尔滨 860

输出结果：深度优先遍历：

海口->昆明->成都->西安->郑州->南京->北京->哈尔滨->

按照图的深度优先搜索的方式来完成这趟旅行，机票开销为3620元

广度优先遍历：

海口->昆明->南京->成都->郑州->北京->西安->哈尔滨->

按照图的广度优先搜索的方式来完成这趟旅行，机票开销为4740元

海口->昆明，昆明->成都，成都->西安，西安->郑州，郑州->北京，郑州->南京，北京->哈尔滨，最小代价完成这趟旅行，开销为3390元）      

二、概要设计

算法设计说明：

图的深度优先遍历和广度优先遍历

深度优先遍历： 类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到（注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点）。

广度优先遍历： 类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

图的最小生成树 prim算法

对顶点操作，在最小生成树的顶点集U和待处理顶点集V-U中，不断地寻找最短边(代价最小)，找到后将对应顶点加入集合U，直到所有顶点均处理完毕(V-U里没有剩余顶点)。

存储结构设计说明：

    邻接矩阵结构体（图结构），存放顶点元素（城市名称）的一维数组，存放权值城市之间距离的邻接矩阵二维数组。

结构体数组：最短路径数组shortedge来存储当前各个顶点之间的最短路径信息，其中的adjvex用于存储最短边的邻接点，lowcost是其对应权值，也就是当前最小的代价。

三、详细设计

1. 根据航班线路和对应的票价将对应的图存储在计算机中；

<1>

typedef struct //邻接矩阵结构体  图结构{VertexType Vertex[VertexMax];             //存放顶点元素（城市名称）的一维数组int AdjMatrix[VertexMax][VertexMax]; //邻接矩阵二维数组（存放权值城市之间的距离）int vexnum, arcnum;                             //图的顶点数和边数} MGraph;

<2>

int LocateVex(MGraph *G, VertexType v) //查找元素v在一维数组 Vertex[] 中的下标，并返回下标{int i;for (i=0;i<G->vexnum;i++){if (v==G->Vertex[i]){return i;}}printf("无该城市!\n");return -1;}

<3>

void CreateUDN(MGraph *G) //构建无向网（Undirected Network）{int i, j;// 1.输入顶点数和边数printf("输入城市个数和航班路线数：\n");printf("城市个数 n=");scanf("%d", &G->vexnum);printf("航班路线数 e=");scanf("%d", &G->arcnum);// 2.输入顶点元素printf("输入城市名称(空格隔开)：");for (i = 0; i < G->vexnum; i++){cin >> G->Vertex[i];//输入顶点元素(城市名)}printf("\n");// 3.矩阵初始化for (i = 0; i < G->vexnum; i++)for (j = 0; j < G->arcnum; j++){G->AdjMatrix[i][j] = MaxInt;}// 4.构建邻接矩阵int n, m;VertexType v1, v2;int w; // v1->v2的权值printf("请输入航班路线和票价(例：海口 长沙 400)：\n");for (i = 0; i < G->arcnum; i++){printf("输入第%d条航班路线及票价: ", i + 1);cin >> v1 >> v2 >> w;  //输入起点终点及机票价格n = LocateVex(G, v1); //获取v1所对应的在Vertex数组中的坐标m = LocateVex(G, v2); //获取v2所对应的在Vertex数组中的坐标G->AdjMatrix[n][m] = w;G->AdjMatrix[m][n] = w; //无向网仅此处不同}}

（2）如果按照图的深度优先搜索的方式来完成这趟旅行，请编程输出依次经过的城市序列，并统计机票开销（手工计算或编程计算均可）；

// 深度优先遍历int sum2arry[VertexMax];void DFS(MGraph *G, int i){int j;visited[i] = 1; //访问过的结点标记为1cout << G->Vertex[i] << "->";  //输出城市名for (j = 0; j < G->vexnum; j++){if (G->AdjMatrix[i][j] != MaxInt && !visited[j]){DFS(G, j);//cout << G->AdjMatrix[i][j] << "\n"; sum2arry[j] = G->AdjMatrix[i][j];          //输出机票价格//printf("%d",sum2arry[j]);}}}void DFStraverse(MGraph *G){for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组为0}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){DFS(G, i);}}int SUM=0;for (int j = 0; j < G->vexnum; j++) //循环计算 深度优先遍历机票开销{SUM += sum2arry[j];if (j == G->vexnum-1 ){printf("\n按照图的深度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}

（3）如果按照图的广度优先搜索的方式来完成这趟旅行，请编程输出依次经过的城市序列，并统计机票开销（手工计算或编程计算均可）；

//广度优先遍历queue<ElemType> Q;int sum1arry[VertexMax];void BFSTraverse(MGraph *G){int k;for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){visited[i] = 1;cout << G->Vertex[i] << "->";Q.push(i);}while (!Q.empty()){k=Q.front();//取队首Q.pop(); //队首弹出for (int j = 0; j < G->vexnum; j++){if (G->AdjMatrix[k][j] != MaxInt && !visited[j]){visited[j] = 1;cout << G->Vertex[j] << "->";Q.push(j);//cout << G->AdjMatrix[k][j] << "\n"; //输出机票价格sum1arry[j] = G->AdjMatrix[k][j];//printf("%d",sum1arry[j]);}}}}int SUM=0;for (int h = 0; h < G->vexnum; h++) //循环计算 广度优先遍历机票开销{SUM += sum1arry[h];if (h == G->vexnum - 1){printf("\n按照图的广度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}

（4）请编程求出该航线图中的最小代价生成树。

//最小生成树int minimal(MGraph *G, ShortEdge *shortedge) //找最短路径的顶点{int i, j;int min, loc;min = MaxInt;for (i = 1; i < G->vexnum; i++){if (min > shortedge[i].lowcost && shortedge[i].lowcost != 0){min = shortedge[i].lowcost;loc = i;}}return loc;}void MiniSpanTree_Prim(MGraph *G, VertexType start) // Prim{int i, j, k;ShortEdge shortedge[VertexMax];// 1.处理起始点startk = LocateVex(G, start);for (i = 0; i < G->vexnum; i++){shortedge[i].adjvex = start;shortedge[i].lowcost = G->AdjMatrix[k][i];}shortedge[k].lowcost = 0; // lowcost为0表示该顶点属于U集合// 2.处理后续结点int sumarry[VertexMax];for (i = 0; i < G->vexnum - 1; i++) //对集合U，去找最短路径的顶点{k = minimal(G, shortedge);                                                                                                                      //找最短路径的顶点cout << shortedge[k].adjvex << "->" << G->Vertex[k] << "," << shortedge[k].lowcost << endl; //输出找到的最短路径顶，及路径权值sumarry[i] = shortedge[k].lowcost;shortedge[k].lowcost = 0;        //将找到的最短路径顶点加入集合U中for (j = 0; j < G->vexnum; j++) // U中加入了新节点，可能出现新的最短路径，故更新shortedge数组{if (G->AdjMatrix[k][j] < shortedge[j].lowcost) //有更短路径出现时，将其替换进shortedge数组{shortedge[j].lowcost = G->AdjMatrix[k][j];shortedge[j].adjvex = G->Vertex[k];}}}for (i = 0; i < G->vexnum - 1; i++){int SUM;SUM += sumarry[i];if (i == G->vexnum - 2)printf("最小代价完成这趟旅行,机票开销为%d元\n", SUM);}}

四、调试分析

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；调试过程中遇到的问题是如何解决：

调试过程遇到了图的深度和广度优先算法无法正常运行的问题

将图一的G->AdjMatrix[i][j]==1改为图二的G->AdjMatrix[i][j]!=MaxInt后程序正常运行。

编写循环语句时，容易漏掉一些条件，导致调试不出正确结果。之后在编程的过程中需要深思熟虑。调试改错的过程中，总是会跳过一些简单的代码，觉得不会错，但往往就是这些简单的代码导致运行出错。所以，在今后调试的过程中，要抱着怀疑一切的态度，认真对待。数组、指针和一些数据结构一块不太熟，还需要加强学习。

（2）算法的时空分析

Prim算法时空分析：

假设总共又n个顶点，那么我肯定有n次比较过程！而在第k次比较过程中，又有n-k个点和另外n-k个顶点相互比较，那么总结起来，那么算法复杂度几乎再n的立方级别。或许有朋友问了，这么算起来，好像也不是很高效哦？n³级别复杂度的确不是很高，但其实prim算法真正效率是介于n²和n³之间的，因为我们如上的分析是一种最坏的情况，就是每个点之间都存在一条路径。再者，相比于穷举法（也就是蛮力法）来查找最小生成树，prim算法已是大大提升了。

图的深度优先遍历和广度优先遍历时空分析：

BFS算法的性能分析
无论是邻接表还是邻接矩阵的存储方式, BFS 算法都需要借助一个辅助队列 Q , n 个顶点均需入队一次,在最坏的情况下,空间 为 O (|V|)。
采用邻接表存储方式时,每个顶点均需搜索一次(或入队一次),故时间复杂度为 O (|V|),在搜索任一顶点的邻接点时,每条边至少访问一次,故时间复杂度为 O (|E|),算法总的时间复杂度为 O (|V|+|E|)。采用邻接矩阵存储方式时,查找每个顶点 邻接点所需的时间为 O (|V|),故算法总
的时间复杂度为O(|V²|).

DFS算法的性能分析
 DFS 算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为 O (|V|)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为 O (|V|),故总的时间复杂度为 O (|V2|)以邻接表表示时,查找所有顶点的邻接点所需的时间为 O (|E|),访问顶点所需的时间为 O (|V|),此时,总的时间复杂度为 O (|V|+|E|).

对于顺序存储结构和链式存储的遍历算法，在时空效率上与进行分析对比，并得出结论：
  链表法时间复杂度较高，空间复杂度较低；数组法时间复杂度较低，空间复杂度较高。因为 数组法一开始就定义好树的大小，如果有空节点就浪费了空间，而链表法不会创建空结点，因此数组法的空间复杂度较高。链表法对指针的操作较繁琐，所需时间长，因此链表法的时间复杂度较低.

（3）经验和体会

由于第一次写这么复杂的程序，开始有点无从下手，在选择合适的数据结构的时候不知道怎么去选，只能一个一个的去试，最后从结合了C语言的结构体和程序需要用到的算法中慢慢摸索到了合适的数据结构，写程序时会出现好多小的语法问题或者逻辑问题，一点点逻辑问题就会让人抓狂。但最后还是静下心来梳理情绪，慢慢的找到了问题。这次的课程设计，巩固了我的编程模块化的思想。模块化降低了程序的耦合性，提高了程序的内聚性；降低了程序复杂度，使程序设计、调试和维护等操作简单化。模块化使得程序设计更加简单和直观，从而提高了程序的易读性和可维护性，而且还可以把程序中经常用到的一些计算或操作编写成通用函数，以供随时调用。

五、运行结果

5.1根据航班线路和对应的票价将对应的图存储在计算机中；

5.2如果按照图的深度和广度优先搜索的方式来完成这趟旅行，请编程输出依次经过的城市序列，并统计机票开销（手工计算或编程计算均可）；

5.3请编程求出该航线图中的最小代价生成树。

六、参考文献  
[1]余艳,刘燕丽.数据结构中递归算法的教学要点及方法探讨. 

严蔚敏等编.数据结构C语言版.北京:清华大学出版社.

[3]张永梅,马礼.程序设计中的递归算法教学探讨.中北大学学报:社会科学版,2001(3):38-39.

[4]冷明,孙凌宇,郭恺强,刘昌鑫,朱平.计算机算法知识领域的深奥理论可视化教学研究——以数据结构与算法课程为例.高等财经教育研究,2014,0(S1):1—3.
[5]孙凌宇,冷明,谭云兰,郁松年.赋权有向图的最小生成树算法凹.计算机工程,2010(2):61—63.
[6]江波,张黎.基于Prim算法的最小生成树优化研究.计算机工程与设计,2009(13):3244—3247.

七、附录

#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <queue>#define VertexMax 20 //最大顶点数为100#define MaxInt 32767 //表示最大整数，表示 ∞using namespace std;typedef int boole;typedef int ElemType;int visited[VertexMax]; //访问标志数组typedef string VertexType; //每个顶点数据类型为字符串型typedef struct //邻接矩阵结构体  图结构{VertexType Vertex[VertexMax];             //存放顶点元素（城市名称）的一维数组int AdjMatrix[VertexMax][VertexMax]; //邻接矩阵二维数组（存放权值城市之间的距离）int vexnum, arcnum;                             //图的顶点数和边数} MGraph;typedef struct //辅助数组结构体(候选最短边){VertexType adjvex; //候选最短边的邻接点int lowcost;     //候选最短边的权值} ShortEdge;int LocateVex(MGraph *G, VertexType v) //查找元素v在一维数组 Vertex[] 中的下标，并返回下标{int i;for (i=0;i<G->vexnum;i++){if (v==G->Vertex[i]){return i;}}printf("无该城市!\n");return -1;}void CreateUDN(MGraph *G) //构建无向网（Undirected Network）{int i, j;// 1.输入顶点数和边数printf("输入城市个数和航班路线数：\n");printf("城市个数 n=");scanf("%d", &G->vexnum);printf("航班路线数 e=");scanf("%d", &G->arcnum);// 2.输入顶点元素printf("输入城市名称(空格隔开)：");for (i = 0; i < G->vexnum; i++){cin >> G->Vertex[i];//输入顶点元素(城市名)}printf("\n");// 3.矩阵初始化for (i = 0; i < G->vexnum; i++)for (j = 0; j < G->arcnum; j++){G->AdjMatrix[i][j] = MaxInt;}// 4.构建邻接矩阵int n, m;VertexType v1, v2;int w; // v1->v2的权值printf("请输入航班路线和票价(例：海口 长沙 400)：\n");for (i = 0; i < G->arcnum; i++){printf("输入第%d条航班路线及票价: ", i + 1);cin >> v1 >> v2 >> w;  //输入起点终点及机票价格n = LocateVex(G, v1); //获取v1所对应的在Vertex数组中的坐标m = LocateVex(G, v2); //获取v2所对应的在Vertex数组中的坐标G->AdjMatrix[n][m] = w;G->AdjMatrix[m][n] = w; //无向网仅此处不同}}// 深度优先遍历int sum2arry[VertexMax];void DFS(MGraph *G, int i){int j;visited[i] = 1; //访问过的结点标记为1cout << G->Vertex[i] << "->";  //输出城市名for (j = 0; j < G->vexnum; j++){if (G->AdjMatrix[i][j] != MaxInt && !visited[j]){DFS(G, j);//cout << G->AdjMatrix[i][j] << "\n"; sum2arry[j] = G->AdjMatrix[i][j];          //输出机票价格//printf("%d",sum2arry[j]);}}}void DFStraverse(MGraph *G){for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组为0}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){DFS(G, i);}}int SUM=0;for (int j = 0; j < G->vexnum; j++) //循环计算 深度优先遍历机票开销{SUM += sum2arry[j];if (j == G->vexnum-1 ){printf("\n按照图的深度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}//广度优先遍历queue<ElemType> Q;int sum1arry[VertexMax];void BFSTraverse(MGraph *G){int k;for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){visited[i] = 1;cout << G->Vertex[i] << "->";Q.push(i);}while (!Q.empty()){k=Q.front();//取队首Q.pop(); //队首弹出for (int j = 0; j < G->vexnum; j++){if (G->AdjMatrix[k][j] != MaxInt && !visited[j]){visited[j] = 1;cout << G->Vertex[j] << "->";Q.push(j);//cout << G->AdjMatrix[k][j] << "\n"; //输出机票价格sum1arry[j] = G->AdjMatrix[k][j];//printf("%d",sum1arry[j]);}}}}int SUM=0;for (int h = 0; h < G->vexnum; h++) //循环计算 广度优先遍历机票开销{SUM += sum1arry[h];if (h == G->vexnum - 1){printf("\n按照图的广度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}//最小生成树int minimal(MGraph *G, ShortEdge *shortedge) //找最短路径的顶点{int i, j;int min, loc;min = MaxInt;for (i = 1; i < G->vexnum; i++){if (min > shortedge[i].lowcost && shortedge[i].lowcost != 0){min = shortedge[i].lowcost;loc = i;}}return loc;}void MiniSpanTree_Prim(MGraph *G, VertexType start) // Prim{int i, j, k;ShortEdge shortedge[VertexMax];// 1.处理起始点startk = LocateVex(G, start);for (i = 0; i < G->vexnum; i++){shortedge[i].adjvex = start;shortedge[i].lowcost = G->AdjMatrix[k][i];}shortedge[k].lowcost = 0; // lowcost为0表示该顶点属于U集合// 2.处理后续结点int sumarry[VertexMax];for (i = 0; i < G->vexnum - 1; i++) //对集合U，去找最短路径的顶点{k = minimal(G, shortedge);                                                                                                                      //找最短路径的顶点cout << shortedge[k].adjvex << "->" << G->Vertex[k] << "," << shortedge[k].lowcost << endl; //输出找到的最短路径顶，及路径权值sumarry[i] = shortedge[k].lowcost;shortedge[k].lowcost = 0;        //将找到的最短路径顶点加入集合U中for (j = 0; j < G->vexnum; j++) // U中加入了新节点，可能出现新的最短路径，故更新shortedge数组{if (G->AdjMatrix[k][j] < shortedge[j].lowcost) //有更短路径出现时，将其替换进shortedge数组{shortedge[j].lowcost = G->AdjMatrix[k][j];shortedge[j].adjvex = G->Vertex[k];}}}for (i = 0; i < G->vexnum - 1; i++){int SUM;SUM += sumarry[i];if (i == G->vexnum - 2)printf("最小代价完成这趟旅行,机票开销为%d元\n", SUM);}}int main(){VertexType start;MGraph G;CreateUDN(&G);printf("\n按照图的深度优先搜索的方式来完成这趟旅行，依次经过的城市序列:\n");DFStraverse(&G);printf("\n按照图的广度优先搜索的方式来完成这趟旅行，依次经过的城市序列:\n");BFSTraverse(&G);printf("\n最小代价完成这趟旅行，依次经过的城市序列:\n");printf("请输入起始点: （例如： 海口）");cin >> start;MiniSpanTree_Prim(&G, start);return 0;}

【Dev

目 录

• 需求分析                                                                                                                        1
• 概要设计                                                                                                                        2
• 详细设计                                                                                                                        3
• 调试分析                                                                                                                        9
• 运行结果                                                                                                                       11
• 参考文献                                                                                                                       12
• 附录                                                                                                                              13

一、需求分析

（1）输入的形式和输入值的范围；

首先构建带权的有向图，输入整数的顶点和边数。即城市的个数，航班路线的条数。再输入图的顶点元素，即城市的名称空格分开（例如：海口 昆明 南京 成都 西安 郑州 北京 哈尔滨）。最后通过输入航班路线（例如：海口 昆明 520 海口 南京 780 海口 成都 660 海口 郑州 830 昆明 成都 380 成都 西安 460 西安 郑州 220 西安 北京 680 南京 郑州 550 南京 北京 630 郑州 北京 400 北京 哈尔滨 860）。

（2）输出的形式；

输出按照图的深度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。

输出按照图的广度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。

输出最小代价完成这趟旅行的城市序列以及机票开销。

（3）程序所能达到的功能；

程序能通过航班路线以及票价的输入，能够输出按照图的深度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。输出按照图的广度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销。输出最小代价完成这趟旅行的城市序列以及机票开销。

（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果：

正确的输入及其输出结果：顶点数、边数、边的信息和权值。输出按照图的深度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销，按照图的广度优先搜索的方式来完成这趟旅行依次经过的城市序列，并输出机票开销，以及最小代价完成这趟旅行的城市序列以及机票开销。

（例如：输入8 12  海口 昆明 南京  成都 西安 郑州 北京 哈尔滨 海口 昆明 520 海口 南京 780 海口 成都 660 海口 郑州 830 昆明 成都 380 成都 西安 460 西安 郑州 220 西安 北京 680 南京 郑州 550 南京 北京 630 郑州 北京 400 北京 哈尔滨 860

输出结果：深度优先遍历：

海口->昆明->成都->西安->郑州->南京->北京->哈尔滨->

按照图的深度优先搜索的方式来完成这趟旅行，机票开销为3620元

广度优先遍历：

海口->昆明->南京->成都->郑州->北京->西安->哈尔滨->

按照图的广度优先搜索的方式来完成这趟旅行，机票开销为4740元

海口->昆明，昆明->成都，成都->西安，西安->郑州，郑州->北京，郑州->南京，北京->哈尔滨，最小代价完成这趟旅行，开销为3390元）      

二、概要设计

算法设计说明：

图的深度优先遍历和广度优先遍历

深度优先遍历： 类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到（注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点）。

广度优先遍历： 类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

图的最小生成树 prim算法

对顶点操作，在最小生成树的顶点集U和待处理顶点集V-U中，不断地寻找最短边(代价最小)，找到后将对应顶点加入集合U，直到所有顶点均处理完毕(V-U里没有剩余顶点)。

存储结构设计说明：

    邻接矩阵结构体（图结构），存放顶点元素（城市名称）的一维数组，存放权值城市之间距离的邻接矩阵二维数组。

结构体数组：最短路径数组shortedge来存储当前各个顶点之间的最短路径信息，其中的adjvex用于存储最短边的邻接点，lowcost是其对应权值，也就是当前最小的代价。

三、详细设计

1. 根据航班线路和对应的票价将对应的图存储在计算机中；

<1>

typedef struct //邻接矩阵结构体  图结构{VertexType Vertex[VertexMax];             //存放顶点元素（城市名称）的一维数组int AdjMatrix[VertexMax][VertexMax]; //邻接矩阵二维数组（存放权值城市之间的距离）int vexnum, arcnum;                             //图的顶点数和边数} MGraph;

<2>

int LocateVex(MGraph *G, VertexType v) //查找元素v在一维数组 Vertex[] 中的下标，并返回下标{int i;for (i=0;i<G->vexnum;i++){if (v==G->Vertex[i]){return i;}}printf("无该城市!\n");return -1;}

<3>

void CreateUDN(MGraph *G) //构建无向网（Undirected Network）{int i, j;// 1.输入顶点数和边数printf("输入城市个数和航班路线数：\n");printf("城市个数 n=");scanf("%d", &G->vexnum);printf("航班路线数 e=");scanf("%d", &G->arcnum);// 2.输入顶点元素printf("输入城市名称(空格隔开)：");for (i = 0; i < G->vexnum; i++){cin >> G->Vertex[i];//输入顶点元素(城市名)}printf("\n");// 3.矩阵初始化for (i = 0; i < G->vexnum; i++)for (j = 0; j < G->arcnum; j++){G->AdjMatrix[i][j] = MaxInt;}// 4.构建邻接矩阵int n, m;VertexType v1, v2;int w; // v1->v2的权值printf("请输入航班路线和票价(例：海口 长沙 400)：\n");for (i = 0; i < G->arcnum; i++){printf("输入第%d条航班路线及票价: ", i + 1);cin >> v1 >> v2 >> w;  //输入起点终点及机票价格n = LocateVex(G, v1); //获取v1所对应的在Vertex数组中的坐标m = LocateVex(G, v2); //获取v2所对应的在Vertex数组中的坐标G->AdjMatrix[n][m] = w;G->AdjMatrix[m][n] = w; //无向网仅此处不同}}

（2）如果按照图的深度优先搜索的方式来完成这趟旅行，请编程输出依次经过的城市序列，并统计机票开销（手工计算或编程计算均可）；

// 深度优先遍历int sum2arry[VertexMax];void DFS(MGraph *G, int i){int j;visited[i] = 1; //访问过的结点标记为1cout << G->Vertex[i] << "->";  //输出城市名for (j = 0; j < G->vexnum; j++){if (G->AdjMatrix[i][j] != MaxInt && !visited[j]){DFS(G, j);//cout << G->AdjMatrix[i][j] << "\n"; sum2arry[j] = G->AdjMatrix[i][j];          //输出机票价格//printf("%d",sum2arry[j]);}}}void DFStraverse(MGraph *G){for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组为0}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){DFS(G, i);}}int SUM=0;for (int j = 0; j < G->vexnum; j++) //循环计算 深度优先遍历机票开销{SUM += sum2arry[j];if (j == G->vexnum-1 ){printf("\n按照图的深度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}

（3）如果按照图的广度优先搜索的方式来完成这趟旅行，请编程输出依次经过的城市序列，并统计机票开销（手工计算或编程计算均可）；

//广度优先遍历queue<ElemType> Q;int sum1arry[VertexMax];void BFSTraverse(MGraph *G){int k;for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){visited[i] = 1;cout << G->Vertex[i] << "->";Q.push(i);}while (!Q.empty()){k=Q.front();//取队首Q.pop(); //队首弹出for (int j = 0; j < G->vexnum; j++){if (G->AdjMatrix[k][j] != MaxInt && !visited[j]){visited[j] = 1;cout << G->Vertex[j] << "->";Q.push(j);//cout << G->AdjMatrix[k][j] << "\n"; //输出机票价格sum1arry[j] = G->AdjMatrix[k][j];//printf("%d",sum1arry[j]);}}}}int SUM=0;for (int h = 0; h < G->vexnum; h++) //循环计算 广度优先遍历机票开销{SUM += sum1arry[h];if (h == G->vexnum - 1){printf("\n按照图的广度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}

（4）请编程求出该航线图中的最小代价生成树。

//最小生成树int minimal(MGraph *G, ShortEdge *shortedge) //找最短路径的顶点{int i, j;int min, loc;min = MaxInt;for (i = 1; i < G->vexnum; i++){if (min > shortedge[i].lowcost && shortedge[i].lowcost != 0){min = shortedge[i].lowcost;loc = i;}}return loc;}void MiniSpanTree_Prim(MGraph *G, VertexType start) // Prim{int i, j, k;ShortEdge shortedge[VertexMax];// 1.处理起始点startk = LocateVex(G, start);for (i = 0; i < G->vexnum; i++){shortedge[i].adjvex = start;shortedge[i].lowcost = G->AdjMatrix[k][i];}shortedge[k].lowcost = 0; // lowcost为0表示该顶点属于U集合// 2.处理后续结点int sumarry[VertexMax];for (i = 0; i < G->vexnum - 1; i++) //对集合U，去找最短路径的顶点{k = minimal(G, shortedge);                                                                                                                      //找最短路径的顶点cout << shortedge[k].adjvex << "->" << G->Vertex[k] << "," << shortedge[k].lowcost << endl; //输出找到的最短路径顶，及路径权值sumarry[i] = shortedge[k].lowcost;shortedge[k].lowcost = 0;        //将找到的最短路径顶点加入集合U中for (j = 0; j < G->vexnum; j++) // U中加入了新节点，可能出现新的最短路径，故更新shortedge数组{if (G->AdjMatrix[k][j] < shortedge[j].lowcost) //有更短路径出现时，将其替换进shortedge数组{shortedge[j].lowcost = G->AdjMatrix[k][j];shortedge[j].adjvex = G->Vertex[k];}}}for (i = 0; i < G->vexnum - 1; i++){int SUM;SUM += sumarry[i];if (i == G->vexnum - 2)printf("最小代价完成这趟旅行,机票开销为%d元\n", SUM);}}

四、调试分析

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；调试过程中遇到的问题是如何解决：

调试过程遇到了图的深度和广度优先算法无法正常运行的问题

将图一的G->AdjMatrix[i][j]==1改为图二的G->AdjMatrix[i][j]!=MaxInt后程序正常运行。

编写循环语句时，容易漏掉一些条件，导致调试不出正确结果。之后在编程的过程中需要深思熟虑。调试改错的过程中，总是会跳过一些简单的代码，觉得不会错，但往往就是这些简单的代码导致运行出错。所以，在今后调试的过程中，要抱着怀疑一切的态度，认真对待。数组、指针和一些数据结构一块不太熟，还需要加强学习。

（2）算法的时空分析

Prim算法时空分析：

假设总共又n个顶点，那么我肯定有n次比较过程！而在第k次比较过程中，又有n-k个点和另外n-k个顶点相互比较，那么总结起来，那么算法复杂度几乎再n的立方级别。或许有朋友问了，这么算起来，好像也不是很高效哦？n³级别复杂度的确不是很高，但其实prim算法真正效率是介于n²和n³之间的，因为我们如上的分析是一种最坏的情况，就是每个点之间都存在一条路径。再者，相比于穷举法（也就是蛮力法）来查找最小生成树，prim算法已是大大提升了。

图的深度优先遍历和广度优先遍历时空分析：

BFS算法的性能分析
无论是邻接表还是邻接矩阵的存储方式, BFS 算法都需要借助一个辅助队列 Q , n 个顶点均需入队一次,在最坏的情况下,空间 为 O (|V|)。
采用邻接表存储方式时,每个顶点均需搜索一次(或入队一次),故时间复杂度为 O (|V|),在搜索任一顶点的邻接点时,每条边至少访问一次,故时间复杂度为 O (|E|),算法总的时间复杂度为 O (|V|+|E|)。采用邻接矩阵存储方式时,查找每个顶点 邻接点所需的时间为 O (|V|),故算法总
的时间复杂度为O(|V²|).

DFS算法的性能分析
 DFS 算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为 O (|V|)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为 O (|V|),故总的时间复杂度为 O (|V2|)以邻接表表示时,查找所有顶点的邻接点所需的时间为 O (|E|),访问顶点所需的时间为 O (|V|),此时,总的时间复杂度为 O (|V|+|E|).

对于顺序存储结构和链式存储的遍历算法，在时空效率上与进行分析对比，并得出结论：
  链表法时间复杂度较高，空间复杂度较低；数组法时间复杂度较低，空间复杂度较高。因为 数组法一开始就定义好树的大小，如果有空节点就浪费了空间，而链表法不会创建空结点，因此数组法的空间复杂度较高。链表法对指针的操作较繁琐，所需时间长，因此链表法的时间复杂度较低.

（3）经验和体会

由于第一次写这么复杂的程序，开始有点无从下手，在选择合适的数据结构的时候不知道怎么去选，只能一个一个的去试，最后从结合了C语言的结构体和程序需要用到的算法中慢慢摸索到了合适的数据结构，写程序时会出现好多小的语法问题或者逻辑问题，一点点逻辑问题就会让人抓狂。但最后还是静下心来梳理情绪，慢慢的找到了问题。这次的课程设计，巩固了我的编程模块化的思想。模块化降低了程序的耦合性，提高了程序的内聚性；降低了程序复杂度，使程序设计、调试和维护等操作简单化。模块化使得程序设计更加简单和直观，从而提高了程序的易读性和可维护性，而且还可以把程序中经常用到的一些计算或操作编写成通用函数，以供随时调用。

五、运行结果

5.1根据航班线路和对应的票价将对应的图存储在计算机中；

5.2如果按照图的深度和广度优先搜索的方式来完成这趟旅行，请编程输出依次经过的城市序列，并统计机票开销（手工计算或编程计算均可）；

5.3请编程求出该航线图中的最小代价生成树。

六、参考文献  
[1]余艳,刘燕丽.数据结构中递归算法的教学要点及方法探讨. 

严蔚敏等编.数据结构C语言版.北京:清华大学出版社.

[3]张永梅,马礼.程序设计中的递归算法教学探讨.中北大学学报:社会科学版,2001(3):38-39.

[4]冷明,孙凌宇,郭恺强,刘昌鑫,朱平.计算机算法知识领域的深奥理论可视化教学研究——以数据结构与算法课程为例.高等财经教育研究,2014,0(S1):1—3.
[5]孙凌宇,冷明,谭云兰,郁松年.赋权有向图的最小生成树算法凹.计算机工程,2010(2):61—63.
[6]江波,张黎.基于Prim算法的最小生成树优化研究.计算机工程与设计,2009(13):3244—3247.

七、附录

#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <queue>#define VertexMax 20 //最大顶点数为100#define MaxInt 32767 //表示最大整数，表示 ∞using namespace std;typedef int boole;typedef int ElemType;int visited[VertexMax]; //访问标志数组typedef string VertexType; //每个顶点数据类型为字符串型typedef struct //邻接矩阵结构体  图结构{VertexType Vertex[VertexMax];             //存放顶点元素（城市名称）的一维数组int AdjMatrix[VertexMax][VertexMax]; //邻接矩阵二维数组（存放权值城市之间的距离）int vexnum, arcnum;                             //图的顶点数和边数} MGraph;typedef struct //辅助数组结构体(候选最短边){VertexType adjvex; //候选最短边的邻接点int lowcost;     //候选最短边的权值} ShortEdge;int LocateVex(MGraph *G, VertexType v) //查找元素v在一维数组 Vertex[] 中的下标，并返回下标{int i;for (i=0;i<G->vexnum;i++){if (v==G->Vertex[i]){return i;}}printf("无该城市!\n");return -1;}void CreateUDN(MGraph *G) //构建无向网（Undirected Network）{int i, j;// 1.输入顶点数和边数printf("输入城市个数和航班路线数：\n");printf("城市个数 n=");scanf("%d", &G->vexnum);printf("航班路线数 e=");scanf("%d", &G->arcnum);// 2.输入顶点元素printf("输入城市名称(空格隔开)：");for (i = 0; i < G->vexnum; i++){cin >> G->Vertex[i];//输入顶点元素(城市名)}printf("\n");// 3.矩阵初始化for (i = 0; i < G->vexnum; i++)for (j = 0; j < G->arcnum; j++){G->AdjMatrix[i][j] = MaxInt;}// 4.构建邻接矩阵int n, m;VertexType v1, v2;int w; // v1->v2的权值printf("请输入航班路线和票价(例：海口 长沙 400)：\n");for (i = 0; i < G->arcnum; i++){printf("输入第%d条航班路线及票价: ", i + 1);cin >> v1 >> v2 >> w;  //输入起点终点及机票价格n = LocateVex(G, v1); //获取v1所对应的在Vertex数组中的坐标m = LocateVex(G, v2); //获取v2所对应的在Vertex数组中的坐标G->AdjMatrix[n][m] = w;G->AdjMatrix[m][n] = w; //无向网仅此处不同}}// 深度优先遍历int sum2arry[VertexMax];void DFS(MGraph *G, int i){int j;visited[i] = 1; //访问过的结点标记为1cout << G->Vertex[i] << "->";  //输出城市名for (j = 0; j < G->vexnum; j++){if (G->AdjMatrix[i][j] != MaxInt && !visited[j]){DFS(G, j);//cout << G->AdjMatrix[i][j] << "\n"; sum2arry[j] = G->AdjMatrix[i][j];          //输出机票价格//printf("%d",sum2arry[j]);}}}void DFStraverse(MGraph *G){for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组为0}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){DFS(G, i);}}int SUM=0;for (int j = 0; j < G->vexnum; j++) //循环计算 深度优先遍历机票开销{SUM += sum2arry[j];if (j == G->vexnum-1 ){printf("\n按照图的深度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}//广度优先遍历queue<ElemType> Q;int sum1arry[VertexMax];void BFSTraverse(MGraph *G){int k;for (int i = 0; i < G->vexnum; i++){visited[i] = 0; //初始化标记数组}for (int i = 0; i < G->vexnum; i++){if (!visited[i]){visited[i] = 1;cout << G->Vertex[i] << "->";Q.push(i);}while (!Q.empty()){k=Q.front();//取队首Q.pop(); //队首弹出for (int j = 0; j < G->vexnum; j++){if (G->AdjMatrix[k][j] != MaxInt && !visited[j]){visited[j] = 1;cout << G->Vertex[j] << "->";Q.push(j);//cout << G->AdjMatrix[k][j] << "\n"; //输出机票价格sum1arry[j] = G->AdjMatrix[k][j];//printf("%d",sum1arry[j]);}}}}int SUM=0;for (int h = 0; h < G->vexnum; h++) //循环计算 广度优先遍历机票开销{SUM += sum1arry[h];if (h == G->vexnum - 1){printf("\n按照图的广度优先搜索的方式来完成这趟旅行，机票开销为%d元\n", SUM);}}}//最小生成树int minimal(MGraph *G, ShortEdge *shortedge) //找最短路径的顶点{int i, j;int min, loc;min = MaxInt;for (i = 1; i < G->vexnum; i++){if (min > shortedge[i].lowcost && shortedge[i].lowcost != 0){min = shortedge[i].lowcost;loc = i;}}return loc;}void MiniSpanTree_Prim(MGraph *G, VertexType start) // Prim{int i, j, k;ShortEdge shortedge[VertexMax];// 1.处理起始点startk = LocateVex(G, start);for (i = 0; i < G->vexnum; i++){shortedge[i].adjvex = start;shortedge[i].lowcost = G->AdjMatrix[k][i];}shortedge[k].lowcost = 0; // lowcost为0表示该顶点属于U集合// 2.处理后续结点int sumarry[VertexMax];for (i = 0; i < G->vexnum - 1; i++) //对集合U，去找最短路径的顶点{k = minimal(G, shortedge);                                                                                                                      //找最短路径的顶点cout << shortedge[k].adjvex << "->" << G->Vertex[k] << "," << shortedge[k].lowcost << endl; //输出找到的最短路径顶，及路径权值sumarry[i] = shortedge[k].lowcost;shortedge[k].lowcost = 0;        //将找到的最短路径顶点加入集合U中for (j = 0; j < G->vexnum; j++) // U中加入了新节点，可能出现新的最短路径，故更新shortedge数组{if (G->AdjMatrix[k][j] < shortedge[j].lowcost) //有更短路径出现时，将其替换进shortedge数组{shortedge[j].lowcost = G->AdjMatrix[k][j];shortedge[j].adjvex = G->Vertex[k];}}}for (i = 0; i < G->vexnum - 1; i++){int SUM;SUM += sumarry[i];if (i == G->vexnum - 2)printf("最小代价完成这趟旅行,机票开销为%d元\n", SUM);}}int main(){VertexType start;MGraph G;CreateUDN(&G);printf("\n按照图的深度优先搜索的方式来完成这趟旅行，依次经过的城市序列:\n");DFStraverse(&G);printf("\n按照图的广度优先搜索的方式来完成这趟旅行，依次经过的城市序列:\n");BFSTraverse(&G);printf("\n最小代价完成这趟旅行，依次经过的城市序列:\n");printf("请输入起始点: （例如： 海口）");cin >> start;MiniSpanTree_Prim(&G, start);return 0;}