/*
*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;
int low_cost;
} Weight[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,char u);
int main(){
UNDGraph G;
cout << "---------创建邻接矩阵---------\n";
create_adjacency_matrix(G);
cout << "---------遍历邻接矩阵---------\n";
ergodic_adjacency_matrix(G);
cout << "---------最小生成树 ---------\n";
int ans = minimun_spanning_tree(G,'A');
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;
}
}
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,char u){
int ans = 0;
int k = get_subscript(G,u);
for(int j = 0;j < G.vertex_num;j++) {
if(j != k) Weight[j] = {u,G.adjacency_martrix[k][j]};
}
Weight[k].low_cost = 0;
for(int i = 1;i < G.vertex_num;i++) {
int min_value = MAXVALUE;
for(int ii = 0;ii < G.vertex_num;ii++) {
if(Weight[ii].low_cost != 0 && Weight[ii].low_cost < min_value) {
min_value = Weight[ii].low_cost;
k = ii;
}
}
cout << Weight[k].front_vertex << " " << G.vertex[k] << endl;
int x = get_subscript(G,Weight[k].front_vertex);
int y = get_subscript(G,G.vertex[k]);
ans += G.adjacency_martrix[x][y];
Weight[k].low_cost = 0;
for(int j = 0;j < G.vertex_num;j++) {
if(G.adjacency_martrix[k][j] < Weight[j].low_cost) {
Weight[j] = {G.vertex[k],G.adjacency_martrix[k][j]};
}
}
}
return ans;
}