1.代码区
/*
*Date: 17-11-30*Author: Qian_Yu
*Program: 克鲁斯卡算法求最小生成树
*/
#include <bits/stdc++.h>
#define MAXVALUE 0x7FFF
#define MAXNUM 0x64
using namespace std;
typedef struct adj_node{
char vertex[MAXNUM];
int adjacency_martrix[MAXNUM][MAXNUM];
int vertex_num,edge_num;
} UNDGraph;
struct node{
char front_vertex;
char after_vertex;
int low_cost;
} Edge[MAXNUM];
void create_adjacency_matrix(UNDGraph &G);
int get_subscript(UNDGraph G,char v);
void ergodic_adjacency_matrix(UNDGraph G);
int minimun_spanning_tree(UNDGraph G);
void fast_sort(struct node Edge[],UNDGraph G);
bool cmp(struct node E1,struct node E2);
int Vexset[MAXNUM];
int main(){
UNDGraph G;
cout << "---------创建邻接矩阵---------\n";
create_adjacency_matrix(G);
cout << "---------遍历邻接矩阵---------\n";
ergodic_adjacency_matrix(G);
cout << "---------最小生成树 ---------\n";
int ans = minimun_spanning_tree(G);
cout << "最小权为:" << ans << endl;
return 0;
}
void create_adjacency_matrix(UNDGraph &G){
cout << "请输入顶点数(int),边数(int):";
cin >> G.vertex_num >> G.edge_num;
cout << "请输入顶点信息(char):";
for(int i = 0;i < G.vertex_num;i++) {
cin >> G.vertex[i];
}
for(int i = 0;i < G.vertex_num;i++) {
for(int j = 0;j < G.vertex_num;j++) {
G.adjacency_martrix[i][j] = MAXVALUE;
}
}
char v1,v2;
int w;
cout << "请输入顶点对V1(char),V2(char):\n";
for(int k = 0;k < G.edge_num;k++) {
cin >> v1 >> v2 >> w;
int i = get_subscript(G,v1);
int j = get_subscript(G,v2);
G.adjacency_martrix[i][j] = w;
G.adjacency_martrix[j][i] = w;
Edge[k].front_vertex = v1;
Edge[k].after_vertex = v2;
Edge[k].low_cost = w;
}
}
int get_subscript(UNDGraph G,char v){
for(int i = 0;i < G.vertex_num;i++) {
if(G.vertex[i] == v) {
return i;
}
}
return -1;
}
void ergodic_adjacency_matrix(UNDGraph G){
for(int i = 0;i < G.vertex_num;i++) {
for(int j = 0;j < G.vertex_num;j++) {
printf(j == 0?"%d":"\t%d",G.adjacency_martrix[i][j]);
}
cout << endl;
}
}
int minimun_spanning_tree(UNDGraph G){
int ans = 0;
//fast_sort(Edge,G);
sort(Edge,Edge + G.edge_num,cmp);
for(int i = 0;i < G.vertex_num;i++) {
Vexset[i] = i;
}
for(int i = 0;i < G.edge_num;i++) {
int v1 = get_subscript(G,Edge[i].front_vertex);
int v2 = get_subscript(G,Edge[i].after_vertex);
int vs1 = Vexset[v1];
int vs2 = Vexset[v2];
if(vs1 != vs2) {
ans += G.adjacency_martrix[v1][v2];
cout << Edge[i].front_vertex << " " << Edge[i].after_vertex << endl;
for(int j = 0;j < G.vertex_num;j++) {
if(Vexset[j] == vs2) {
Vexset[j] = vs1;
}
}
}
}
return ans;
}
//void fast_sort(struct node Edge[],UNDGraph G){
// for(int i = 0;i < G.edge_num - 1;i++) {
// int min = i;
// for(int j = i + 1;j < G.edge_num;j++) {
// if(Edge[j].low_cost < Edge[min].low_cost) {
// min = j;
// }
// }
// if(min != i) {
// struct node ec = Edge[i];
// Edge[i] = Edge[min];
// Edge[min] = ec;
// }
// }
//}
bool cmp(struct node E1,struct node E2){
return E1.low_cost < E2.low_cost;
}
2.结果区
