图是这样的
图片来源:
添加链接描述
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
struct edge {
edge() {}
edge(char s, char e, int w) :start(s), end(e), weight(w) {}
bool operator<(edge x1) {
return weight < x1.weight;
}
char start, end;
int weight;
};
class Graph
{
public:
char Find_Set(char c);
void Union(char c1, char c2);
void Kruskal();
void Prim(char C);
vector<edge> Kruskal_result;
vector<edge> Kruskal_edge;
map<char, char> Kruskal_vertex;
map<char, pair<char,int>> Prim_result;
map<char, vector<pair<char, int>>> Prim_edge;;
map<char, pair<int, int>> Prim_vertex; //key visited weight
};
char Graph::Find_Set(char c)
{
char p = Kruskal_vertex[c];
while (p != Kruskal_vertex[p])
p = Kruskal_vertex[p];
return p;
}
void Graph::Union(char c1, char c2)
{
char t1 = Find_Set(c1);
char t2 = Find_Set(c2);
Kruskal_vertex[t2] = t1;
}
void Graph::Kruskal()
{
for (vector<edge>::iterator i = Kruskal_edge.begin(); i != Kruskal_edge.end(); i++) {
if (Find_Set((*i).start) != Find_Set((*i).end)) {
Kruskal_result.push_back((*i));
Union((*i).start, (*i).end);
}
}
}
void Graph::Prim(char C) //起点
{
map<char, int> Q;
Prim_vertex[C].first = 1; //visited
Prim_vertex[C].second = 0; //dist = 0
Prim_result[C].first = C;
for (map<char, pair<int, int>>::iterator i = Prim_vertex.begin(); i != Prim_vertex.end(); i++) {
Q[(*i).first] = (*i).second.second;
}
while (!Q.empty()){
char temp;
int value = INT_MAX;
for (map<char, int>::iterator i = Q.begin(); i != Q.end(); i++) {
if (value > (*i).second) {
temp = (*i).first;
value = (*i).second;
}
}
map<char, int>::iterator E = Q.find(temp);
Q.erase(E);
Prim_vertex[temp].first = 1;
int size = Prim_edge[temp].size();
for (int i = 0; i < size; i++) {
if (!Prim_vertex[Prim_edge[temp][i].first].first && Prim_vertex[Prim_edge[temp][i].first].second > Prim_edge[temp][i].second){
Prim_vertex[Prim_edge[temp][i].first].second = Prim_edge[temp][i].second;
Q[Prim_edge[temp][i].first] = Prim_edge[temp][i].second;
Prim_result[Prim_edge[temp][i].first].first = temp;
Prim_result[Prim_edge[temp][i].first].second = Prim_edge[temp][i].second;
}
}
}
}
int main()
{
Graph G;
int n, m, weight;
char c, start, end;
cin >> n >> m;
while (n--) {
cin >> c;
G.Kruskal_vertex[c] = c;
G.Prim_vertex[c].first = 0; //visited
G.Prim_vertex[c].second = INT_MAX; //dist
}
while (m--) {
cin >> start >> end >> weight;
G.Kruskal_edge.push_back(edge(start, end, weight));
G.Prim_edge[start].push_back(make_pair(end, weight));
G.Prim_edge[end].push_back(make_pair(start, weight));
}
sort(G.Kruskal_edge.begin(), G.Kruskal_edge.end());
G.Kruskal();
cout << endl << endl;
int size = G.Kruskal_result.size();
cout << "Kruskal:" << endl;
for (int i = 0; i < size; i++)
cout << G.Kruskal_result[i].start << ' ' << G.Kruskal_result[i].end << ' ' << G.Kruskal_result[i].weight << endl;
cout << endl << endl;
start = 'a';
G.Prim(start);
cout << "Prim:" << endl;
for (map<char, pair<char, int>>::iterator i = G.Prim_result.begin(); i != G.Prim_result.end(); i++) {
if ((*i).first == start) continue;
cout << (*i).first << ' ' << (*i).second.first << ' ' << (*i).second.second << endl;
}
cout << endl << endl;
}