#include<iostream>
#include<string>
#include<vector>
#include <climits>
using namespace std;
struct Graph {
int vexnum;
int edge;
int** arc;
string* information;
};
void createGraph(Graph& g) {
cout << "请输入顶点数:";
cin >> g.vexnum;
cout << "请输入边的条数:";
cin >> g.edge;
g.information = new string[g.vexnum];
g.arc = new int* [g.vexnum];
for (int i = 0; i < g.vexnum; i++) {
g.arc[i] = new int[g.vexnum];
cout << "请输入顶点 " << i + 1 << " 的城市名: ";
getline(cin, g.information[i]);
for (int k = 0; k < g.vexnum; k++) {
g.arc[i][k] = INT_MAX;
}
}
cout << "请输入每条边的起点和终点城市名(输入完成后输入两个空字符串结束):" << endl;
string start, end;
while (cin >> start >> end) {
if (start.empty() || end.empty()) break;
int start_index = -1, end_index = -1;
for (int i = 0; i < g.vexnum; ++i) {
if (g.information[i] == start) start_index = i;
if (g.information[i] == end) end_index = i;
}
if (start_index == -1 || end_index == -1) {
cout << "城市名输入错误,请输入有效的城市名。" << endl;
continue;
}
int weight;
cin >> weight;
g.arc[start_index][end_index] = weight;
g.arc[end_index][start_index] = weight;
}
}
void print(Graph g) {
cout << "城市名\t";
for (int i = 0; i < g.vexnum; i++) {
cout << g.information[i] << "\t";
}
cout << endl;
for (int i = 0; i < g.vexnum; i++) {
cout << g.information[i] << "\t";
for (int j = 0; j < g.vexnum; j++) {
if (g.arc[i][j] == INT_MAX)
cout << "∞\t";
else
cout << g.arc[i][j] << "\t";
}
cout << endl;
}
}
struct Assis_array {
int start;
int end;
int weight;
};
void Prim(Graph g, int begin) {
Assis_array* close_edge = new Assis_array[g.vexnum];
int min, end, start;
for (int j = 0; j < g.vexnum; j++) {
if (j != begin) {
close_edge[j].start = begin;
close_edge[j].end = j;
close_edge[j].weight = g.arc[begin][j];
}
}
close_edge[begin].weight = INT_MAX;
for (int j = 1; j < g.vexnum; j++) {
min = INT_MAX;
end = start = -1;
for (int k = 0; k < g.vexnum; k++) {
if (close_edge[k].weight < min) {
min = close_edge[k].weight;
end = close_edge[k].end;
start = close_edge[k].start;
}
}
if (min != INT_MAX) {
cout << g.information[start] << " - " << g.information[end]
<< " : " << min << endl;
close_edge[end].weight = INT_MAX;
}
else {
break;
}
for (int k = 0; k < g.vexnum; k++) {
if (g.arc[end][k] < close_edge[k].weight && close_edge[k].weight != INT_MAX) {
close_edge[k].weight = g.arc[end][k];
close_edge[k].start = end;
}
}
}
delete[] close_edge;
}
int main()
{
Graph g;
createGraph(g);
print(g);
Prim(g, 1);
system("pause");
return 0;
}