#include <iostream> using namespace std; #include <iomanip> #define OK 1 #define MaxInt 32767 #define MVNum 100 typedef int Status; typedef char VerTexType; typedef int ArcType; typedef struct { VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum, arcnum; } MGraph; struct Edge { VerTexType Head; VerTexType Tail; ArcType lowcost; } Edge[(MVNum * (MVNum - 1)) / 2]; int Vexset[MVNum]; Status LocateVex(MGraph G, VerTexType e) { int i; for (i = 0; i < G.vexnum; i++) if (G.vexs[i] == e) return i; } Status CreateUDN(MGraph &G) { int i, j, k, w; char v1, v2; cout << "输入顶点个数和边的条数:"; cin >> G.vexnum >> G.arcnum; cout << "输入各个顶点:"; for (i = 0; i < G.vexnum; i++) cin >> G.vexs[i]; for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = MaxInt; for (k = 0; k < G.arcnum; k++) { cout << "输入一条边依附的顶点和权值:"; cin >> v1 >> v2 >> w; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = w; G.arcs[j][i] = G.arcs[i][j]; Edge[k].lowcost = w; Edge[k].Head = v1; Edge[k].Tail = v2; } return OK; } void DispGraph(MGraph G) { int i, j; cout << "顶点:\n"; for (i = 0; i < G.vexnum; i++) cout << G.vexs[i] << " "; cout << "\n邻接矩阵:\n"; for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) cout << setw(7) << G.arcs[i][j]; cout << endl; } } Status Min(MGraph G) { int i, index = -1, min = MaxInt; for (i = 0; i < G.vexnum; i++) { if (Edge[i].lowcost < min && Edge[i].lowcost != 0) { min = Edge[i].lowcost; index = i; } } return index; } void Sort(MGraph G) { //冒泡排序 int m = G.arcnum - 2; struct Edge t; int flag = 1; while ((m > 0) && flag == 1) { flag = 0; for (int j = 0; j <= m; j++) { if (Edge[j].lowcost > Edge[j + 1].lowcost) { flag = 1; t = Edge[j]; Edge[j] = Edge[j + 1]; Edge[j + 1] = t; }//if }//for --m; }//while }//Sort void MiniSpanTree_Kruskal(MGraph G) { int i, j; int v1, v2, vs1 Sort(G); for (i = 0; i < G.vexnum; i++) Vexset[i] = i; for (i = 0; i < G.arcnum; i++) { v1 = LocateVex(G, Edge[i].Head); v2 = LocateVex(G, Edge[i].Tail); vs1 = Vexset[v1]; vs2 = Vexset[v2]; if (vs1 != vs2) { cout << Edge[i].Head << Edge[i].Tail << endl; for (j = 0; j < G.vexnum; j++) if (Vexset[j] == vs2) Vexset[j] = vs1; } } } int main() { MGraph G; CreateUDN(G); DispGraph(G); cout << "最小生成树的边如下:" << endl; MiniSpanTree_Kruskal(G); return 0; } 函数前写注释
理解问题#include <iostream> using namespace std; #include <iomanip> #define OK 1 #define MaxInt 32767 #define MVNum 100 typedef int Status; typedef char VerTexType; typedef int ArcType; typedef struct { VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum, arcnum; } MGraph; struct Edge { VerTexType Head; VerTexType Tail; ArcType lowcost; } Edge[(MVNum * (MVNum - 1)) / 2]; int Vexset[MVNum]; Status LocateVex(MGraph G, VerTexType e) { int i; for (i = 0; i < G.vexnum; i++) if (G.vexs[i] == e) return i; } Status CreateUDN(MGraph &G) { int i, j, k, w; char v1, v2; cout << "输入顶点个数和边的条数:"; cin >> G.vexnum >> G.arcnum; cout << "输入各个顶点:"; for (i = 0; i < G.vexnum; i++) cin >> G.vexs[i]; for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = MaxInt; for (k = 0; k < G.arcnum; k++) { cout << "输入一条边依附的顶点和权值:"; cin >> v1 >> v2 >> w; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = w; G.arcs[j][i] = G.arcs[i][j]; Edge[k].lowcost = w; Edge[k].Head = v1; Edge[k].Tail = v2; } return OK; } void DispGraph(MGraph G) { int i, j; cout << "顶点:\n"; for (i = 0; i < G.vexnum; i++) cout << G.vexs[i] << " "; cout << "\n邻接矩阵:\n"; for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) cout << setw(7) << G.arcs[i][j]; cout << endl; } } Status Min(MGraph G) { int i, index = -1, min = MaxInt; for (i = 0; i < G.vexnum; i++) { if (Edge[i].lowcost < min && Edge[i].lowcost != 0) { min = Edge[i].lowcost; index = i; } } return index; } void Sort(MGraph G) { //冒泡排序 int m = G.arcnum - 2; struct Edge t; int flag = 1; while ((m > 0) && flag == 1) { flag = 0; for (int j = 0; j <= m; j++) { if (Edge[j].lowcost > Edge[j + 1].lowcost) { flag = 1; t = Edge[j]; Edge[j] = Edge[j + 1]; Edge[j + 1] = t; }//if }//for --m; }//while }//Sort void MiniSpanTree_Kruskal(MGraph G) { int i, j; int v1, v2, vs1 Sort(G); for (i = 0; i < G.vexnum; i++) Vexset[i] = i; for (i = 0; i < G.arcnum; i++) { v1 = LocateVex(G, Edge[i].Head); v2 = LocateVex(G, Edge[i].Tail); vs1 = Vexset[v1]; vs2 = Vexset[v2]; if (vs1 != vs2) { cout << Edge[i].Head << Edge[i].Tail << endl; for (j = 0; j < G.vexnum; j++) if (Vexset[j] == vs2) Vexset[j] = vs1; } } } int main() { MGraph G; CreateUDN(G); DispGraph(G); cout << "最小生成树的边如下:" << endl; MiniSpanTree_Kruskal(G); return 0; } 函数前写注释
已完成理解「#include <iostream> using namespace std; #include <iomanip> #define OK 1 #define MaxInt 32767 #define MVNum 100 typedef int Status; typedef char VerTexType; typedef int ArcType; typedef struct { VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum, arcnum; } MGraph; struct Edge { VerTexType Head; VerTexType Tail; ArcType lowcost; } Edge[(MVNum * (MVNum - 1)) / 2]; int Vexset[MVNum]; Status LocateVex(MGraph G, VerTexType e) { int i; for (i = 0; i < G.vexnum; i++) if (G.vexs[i] == e) return i; } Status CreateUDN(MGraph &G) { int i, j, k, w; char v1, v2; cout << "输入顶点个数和边的条数:"; cin >> G.vexnum >> G.arcnum; cout << "输入各个顶点:"; for (i = 0; i < G.vexnum; i++) cin >> G.vexs[i]; for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = MaxInt; for (k = 0; k < G.arcnum; k++) { cout << "输入一条边依附的顶点和权值:"; cin >> v1 >> v2 >> w; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = w; G.arcs[j][i] = G.arcs[i][j]; Edge[k].lowcost = w; Edge[k].Head = v1; Edge[k].Tail = v2; } return OK; } void DispGraph(MGraph G) { int i, j; cout << "顶点:\n"; for (i = 0; i < G.vexnum; i++) cout << G.vexs[i] << " "; cout << "\n邻接矩阵:\n"; for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) cout << setw(7) << G.arcs[i][j]; cout << endl; } } Status Min(MGraph G) { int i, index = -1, min = MaxInt; for (i = 0; i < G.vexnum; i++) { if (Edge[i].lowcost < min && Edge[i].lowcost != 0) { min = Edge[i].lowcost; index = i; } } return index; } void Sort(MGraph G) { //冒泡排序 int m = G.arcnum - 2; struct Edge t; int flag = 1; while ((m > 0) && flag == 1) { flag = 0; for (int j = 0; j <= m; j++) { if (Edge[j].lowcost > Edge[j + 1].lowcost) { flag = 1; t = Edge[j]; Edge[j] = Edge[j + 1]; Edge[j + 1] = t; }//if }//for --m; }//while }//Sort void MiniSpanTree_Kruskal(MGraph G) { int i, j; int v1, v2, vs1 Sort(G); for (i = 0; i < G.vexnum; i++) Vexset[i] = i; for (i = 0; i < G.arcnum; i++) { v1 = LocateVex(G, Edge[i].Head); v2 = LocateVex(G, Edge[i].Tail); vs1 = Vexset[v1]; vs2 = Vexset[v2]; if (vs1 != vs2) { cout << Edge[i].Head << Edge[i].Tail << endl; for (j = 0; j < G.vexnum; j++) if (Vexset[j] == vs2) Vexset[j] = vs1; } } } int main() { MGraph G; CreateUDN(G); DispGraph(G); cout << "最小生成树的边如下:" << endl; MiniSpanTree_Kruskal(G); return 0; } 函数前写注释」
展开阅读网页