要求：
（1）采用邻接矩阵/邻接表建立图；
（2）采用深度优先/广度优先搜索方式遍历图；
（3）编程实现Dijkstra最短路径算法。
#include <iostream> #include <string> #define MaxInt 32767 #define MVNum 100 typedef int Status; typedef char VertexType; typedef int ArcType; using namespace std; typedef struct { VertexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum, arcnum; }AMGraph; struct Dis { string path; int value; bool visit; Dis() { visit = false; value = 0; path = ""; } }; Dis *dis; //定位 Status LocateVex(AMGraph G, VertexType u) { int i; for (i = 0; i < G.vexnum; ++i) { if (u == G.vexs[i]) { return i; } } return -1; } //有向图的邻接矩阵创建 Status CreateUDN(AMGraph& G) { cout << "请输入总定点数，总边数: "; cin >> G.vexnum >> G.arcnum; cout << "请输入顶点信息: "; for (int i = 0; i < G.vexnum; ++i) { cin >> G.vexs[i]; } for (int i = 0; i < G.vexnum; ++i) { for (int j = 0; j < G.vexnum; ++j) { G.arcs[i][j] = MaxInt; } } for (int k = 0; k < G.arcnum; ++k) { int i, j; char v1, v2; int w; cout << "请输入第" << k + 1 << "边的顶点和权值: "; cin >> v1 >> v2 ; cin >> w; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = w; //G.arcs[j][i] = G.arcs[i][j]; } dis = new Dis[MVNum]; return 1; } //邻接矩阵深度优先 //void DFS_AM(AMGraph G, int v) //{ // cout << v << " "; // visited[v] = true; // for (int w = 0; w < G.vexnum; w++) // { // if ((G.arcs[v][w] != MaxInt) && (!visited[w])) // { // DFS_AM(G, w); // } // } //} bool visitDFS[MVNum]; void DFS(AMGraph G, int i) { int j; visitDFS[i] = true; cout<<G.vexs[i]<<" "; for (j = 0; j < G.vexnum; j++) { if (G.arcs[i][j] != MVNum && !visitDFS[j]) DFS(G, j); } } void DFS_AM(AMGraph G) { int i; for (i = 0; i < G.vexnum; i++) visitDFS[i] = false; for (i = 0; i < G.vexnum; i++) { if (!visitDFS[i]) DFS(G, i); } } //Dijkstra算法 //void ShortestPath(AMGraph G, int v0) //{ // bool S[MVNum]; // int D[MVNum]; // int Path[MVNum]; // int n = G.vexnum; // for (int v = 0; v < n; ++v) // { // S[v] = false; // D[v] = G.arcs[v0][v]; // if (D[v] < MaxInt) // { // Path[v] = v0; // } // else // Path[v] = -1; // } // S[v0] = true; // D[v0] = 0; // for (int i = 1; i < n; ++i) // { // int v = 0; // int min = MaxInt; // for (int w = 0; w < n; ++w) // { // if (!S[w] && D[w] < min) // { // v = w; // min = D[w]; // } // } // S[v] = true; // for (int w = 0; w < n; ++w) // { // if (!S[w] && (D[v] + G.arcs[v][w] < D[w])) // { // D[w] = D[v] + G.arcs[v][w]; // Path[w] = v; // } // } // } // for (int i = 1; i <= n; i++) // { // cout << D[i] << " "; // } //} void Dijkstra(AMGraph G, int begin) { //首先初始化我们的dis数组 int i; for (i = 0; i < G.vexnum; i++) { //设置当前的路径 dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1); dis[i].value = G.arcs[begin - 1][i]; } //设置起点的到起点的路径为0 dis[begin - 1].value = 0; dis[begin - 1].visit = true; int count = 1; //计算剩余的顶点的最短路径（剩余this->vexnum-1个顶点） while (count != G.vexnum) { //temp用于保存当前dis数组中最小的那个下标 //min记录的当前的最小值 int temp = 0; int min = MaxInt; for (i = 0; i < G.vexnum; i++) { if (!dis[i].visit && dis[i].value < min) { min = dis[i].value; temp = i; } } //把temp对应的顶点加入到已经找到的最短路径的集合中 dis[temp].visit = true; ++count; for (i = 0; i < G.vexnum; i++) { //注意这里的条件arc[temp][i]!=INT_MAX必须加，不然会出现溢出，从而造成程序异常 if (!dis[i].visit && G.arcs[temp][i] != MaxInt && (dis[temp].value + G.arcs[temp][i]) < dis[i].value) { //如果新得到的边可以影响其他为访问的顶点，那就就更新它的最短路径和长度 dis[i].value = dis[temp].value + G.arcs[temp][i]; dis[i].path = dis[temp].path + "-->v" + to_string(i + 1); } } } } void print_path(AMGraph G, int begin) { string str; str = "v" + to_string(begin); cout << "以" << str << "为起点的图的最短路径为：" << endl; for (int i = 0; i != G.vexnum; i++) { if (dis[i].value != MaxInt) cout << dis[i].path << "=" << dis[i].value << endl; else { cout << dis[i].path << "是无最短路径的" << endl; } } } void Graphprint(AMGraph G) { cout << "图的邻接矩阵为：" << endl; int count_row = 0; //打印行的标签 int count_col = 0; //打印列的标签 //开始打印 while (count_row != G.vexnum) { count_col = 0; while (count_col != G.vexnum) { if (G.arcs[count_row][count_col] == MaxInt) cout << "∞" << " "; else cout << G.arcs[count_row][count_col] << " "; ++count_col; } cout << endl; ++count_row; } } int main() { int v; AMGraph G; CreateUDN(G); cout << "邻接矩阵为" << endl; Graphprint(G); cout << "深度优先遍历结果：" << endl; DFS_AM(G); cout << endl; cout << "请输入最短路径起始点：" << endl; cin >> v; Dijkstra(G, v); cout << "最短路径为：" << endl; print_path(G, v); return 0; }