数据结构课程设计/校园导游程序及通信线路设计 #1
在上一章节，我们成功进行了菜单页面的搭建，存储结构的设计和图的初始化，现在，让我们开始解决第一个问题。
第一问：
为来访的客人提供图中任意景点相关信息的查询。
这一问比较简单，我们只需要将图传入一个函数中，并根据用户的输入（节点的编号）进行相对应信息的查询即可。
// 查找景点信息的函数void queryScenicInfo(MGraph &G) { while (true) { showMenu(); // 打印图 cout << "请选择要查寻的景点代号,输入END结束（例: A）: "; string scenic_choice; cin >> scenic_choice; // 用户的选择 bool found = false; if(scenic_choice == "END"){ cout<<"退出查询"<<endl; return; } for (int i = 0; i < G.vexnum; i++) { // 查找匹配的景点名称 if (G.vArray[i].nickname == scenic_choice) { // 查询到顶点的代号。 found = true; cout << "查询到 " << G.vArray[i].name << " 的以下信息:" << endl; cout << "功能简介: " << G.vArray[i].data << endl; cout << "毗邻景点: "; Node* arc = G.vArray[i].firstarc; while (arc != NULL) { cout << G.vArray[arc->index].name << " "; arc = arc->next; } cout << endl; break; } } // 如果没有找到对应的景点 if (!found) { cout << "---------------输入不合法--------------" << endl; } system("pause"); system("cls"); }}
这里也相对应的做了防误输入的处理，在检测到用户输入的节点编号后将其打印即可。查找操作用了简单的顺序查找，可以使用效率更高的折半查找等。
现在你可以在主菜单 switch 中取消相关函数的注释，来查看一下效果。
第二问：
从第二问开始就要上一些强度了，查询任意两个顶点的最短路径，我们可以使用Floyd弗洛伊德算法来存储每一对顶点的最短路径，但是这个算法的前提是djstl迪杰斯特拉算法，因此编者这里干脆设计成根据用户输入的两个顶点实时使用迪杰斯特拉算法计算出来，就不进行floyd算法来初始化了。 首先我们进行用户输入的设计：
void queryPath(MGraph &G) { int obj = -1; cout<<"请输入起始路径编号(例:A)>>"; string fd; cin>>fd; cout<<"请输入终止路径编号>>" ; string fde; cin>>fde; cout << "正在查询景点路径..." << endl; for (int i = 0; i < G.vexnum; i++) { if (fd == G.vArray[i].nickname) { obj = i; // 寻找目标节点下标 break; } } if (obj == -1) { cout << "未找到源点!" << endl; return; } int obje = -1; for (int i = 0; i < G.vexnum; i++) { if (fde == G.vArray[i].nickname) { obje = i; // 寻找目标节点下标 break; } } if (obje == -1) { cout << "未找到终点!" << endl; return; }
现在obj和obje分别存储了用户输入的起点和终点，进入核心算法部分。
在编者的这篇文章中详细讲解了djstl算法的实现：
有一定基础的同学可以听我下面的简述
初始化：首先，定义了一个源点 fd，并通过遍历图中的顶点名称来找出源点在数组中的索引（即顶点的编号）。接着，初始化一些辅助数组： P[maxv]：前驱节点数组，用来记录最短路径中每个节点的前驱节点。 D[maxv]：距离数组，用来记录源点到每个顶点的最短距离。初始时，所有顶点的距离设置为无穷大（no），源点的距离为 0。 final[maxv]：标记数组，用来记录哪些节点已经包含在最短路径集合中。最初，源点被标记为已确定。
int maxv = G.vexnum; int P[maxv]; // 前驱节点数组 int D[maxv]; // 距离数组 bool final[maxv]; // 标记节点是否已加入最短路径集合 // 初始化数组 fill(P, P + maxv, 0); fill(D, D + maxv, no); fill(final, final + maxv, false); D[obj] = 0; // 源点到源点的距离为0 final[obj] = true; // 源点加入最短路径集合
算法的核心部分是一个迭代过程，循环 vexnum - 1 次，每次找到距离当前最短的未处理节点，并更新该节点的邻接点的最短路径。 每次迭代，找到一个未处理节点（即距离最小的节点）并加入最短路径集合。 更新与该节点相邻的所有节点的距离。如果某个节点通过当前节点可以得到更短的路径，就更新该节点的最短距离和前驱节点。 终止条件：如果在某次迭代中无法找到距离最小的未处理节点，说明剩余的节点不可达，算法结束。
下面进入算法的核心部分：
// 初始化 D 和 P 数组（邻接点的距离赋值） Node* node = G.vArray[obj].firstarc; while (node != NULL) { D[node->index] = node->distance; P[node->index] = obj; node = node->next; }
初始化d和p数组，然后进入主循环：
// 主循环，循环vexnum-1次，每次确定一个节点的最短路径 for (int i = 1; i < G.vexnum; i++) { int j = -1; int min = no; // 在未确定最短路径的节点中选择距离最小的节点 for (int k = 0; k < G.vexnum; k++) { if (!final[k] && D[k] < min) { j = k; min = D[k]; } } if (j == -1) break; final[j] = true; // 将顶点 j 加入已确定最短路径集合 // 更新与 j 节点相邻的节点的最短路径 node = G.vArray[j].firstarc; while (node != NULL) { int jk = D[j] + node->distance; // 计算经过节点 j 到相邻节点的路径长度 if (!final[node->index] && jk < D[node->index]) { // 如果更短，更新路径和前驱节点 D[node->index] = jk; P[node->index] = j; } node = node->next; } }
在这个循环中，我们每次加入一个最短的顶点，并以此顶点为 中转 更新其他顶点的距离。
最后我们打印出这个最短路径。
// 输出最短路径结果 for (int i = 0; i < G.vexnum; i++) { if (G.vArray[i].nickname == fde) { if (D[i] == no) { cout << "无法到达 " << G.vArray[i].name << endl; } else { cout << "最短路径到 " << G.vArray[i].name << " : 路径长度 = " << D[i] << endl; int pre = P[i]; vector<string> path; path.push_back(G.vArray[i].name); // 先加入终点 while (pre != 0) { path.push_back(G.vArray[pre].name); pre = P[pre]; } for (int j = path.size() - 1; j >= 0; --j) { cout << path[j]; if (j > 0) cout << "->"; } cout << endl; } } }}
以下是这个函数的完整代码，以上步骤有问题的同学可以看看完整代码：
void queryPath(MGraph &G) { int obj = -1; cout<<"请输入起始路径编号(例:A)>>"; string fd; cin>>fd; cout<<"请输入终止路径编号>>" ; string fde; cin>>fde; cout << "正在查询景点路径..." << endl; for (int i = 0; i < G.vexnum; i++) { if (fd == G.vArray[i].nickname) { obj = i; // 寻找目标节点下标 break; } } if (obj == -1) { cout << "未找到源点!" << endl; return; } int obje = -1; for (int i = 0; i < G.vexnum; i++) { if (fde == G.vArray[i].nickname) { obje = i; // 寻找目标节点下标 break; } } if (obje == -1) { cout << "未找到终点!" << endl; return; } int maxv = G.vexnum; int P[maxv]; // 前驱节点数组 int D[maxv]; // 距离数组 bool final[maxv]; // 标记节点是否已加入最短路径集合 // 初始化数组 fill(P, P + maxv, 0); fill(D, D + maxv, no); fill(final, final + maxv, false); D[obj] = 0; // 源点到源点的距离为0 final[obj] = true; // 源点加入最短路径集合 // 初始化 D 和 P 数组（邻接点的距离赋值） Node* node = G.vArray[obj].firstarc; while (node != NULL) { D[node->index] = node->distance; P[node->index] = obj; node = node->next; } // 主循环，循环vexnum-1次，每次确定一个节点的最短路径 for (int i = 1; i < G.vexnum; i++) { int j = -1; int min = no; // 在未确定最短路径的节点中选择距离最小的节点 for (int k = 0; k < G.vexnum; k++) { if (!final[k] && D[k] < min) { j = k; min = D[k]; } } if (j == -1) break; final[j] = true; // 将顶点 j 加入已确定最短路径集合 // 更新与 j 节点相邻的节点的最短路径 node = G.vArray[j].firstarc; while (node != NULL) { int jk = D[j] + node->distance; // 计算经过节点 j 到相邻节点的路径长度 if (!final[node->index] && jk < D[node->index]) { // 如果更短，更新路径和前驱节点 D[node->index] = jk; P[node->index] = j; } node = node->next; } } // 输出最短路径结果 for (int i = 0; i < G.vexnum; i++) { if (G.vArray[i].nickname == fde) { if (D[i] == no) { cout << "无法到达 " << G.vArray[i].name << endl; } else { cout << "最短路径到 " << G.vArray[i].name << " : 路径长度 = " << D[i] << endl; int pre = P[i]; vector<string> path; path.push_back(G.vArray[i].name); // 先加入终点 while (pre != 0) { path.push_back(G.vArray[pre].name); pre = P[pre]; } for (int j = path.size() - 1; j >= 0; --j) { cout << path[j]; if (j > 0) cout << "->"; } cout << endl; } } }}
现在可以取消菜单中函数的注释，尝试一下函数功能：
在下一节我们将会实现第三个问题。