// Keruskal
#include "stdafx.h"
#include<iostream>
using namespace std;
#define OK 1
#define ERROR -1
#define MAXINT 32767
#define MAXNUM 100
typedef char VerTexType;
typedef int ArcType;
typedef struct {
VerTexType vexs[MAXNUM];
ArcType arcs[MAXNUM][MAXNUM];
int vexnum, arcnum;
}AMGraph;
struct {
VerTexType Head;
VerTexType Tail;
ArcType lowcost;
}Edge[MAXNUM * MAXNUM / 2];
int LocateVex(AMGraph G, VerTexType e) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == e) {
return i;
}
}
return ERROR;
}
void Create_AMGraph(AMGraph &G) {
cout << "输入要构造的顶点数，边数";
cin >> G.vexnum >> G.arcnum;
for (int i = 0; i < G.vexnum; i++) {
cout << "输入第" << i + 1 << "个顶点";
cin >> G.vexs[i];
}
for (int i = 0; i < G.vexnum; ++i) //初始化邻接矩阵，边的权值均置为极大值MaxInt
for (int j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = MAXINT;
for (int i = 0; i < G.arcnum; i++) {
char s1, s2;
int dir1, dir2;
int width;
cout << "输入第" << i + 1 << "条边的顶点及权值大小";
cin >> s1 >> s2 >> width;
dir1 = LocateVex(G, s1); dir2 = LocateVex(G, s2);
G.arcs[dir1][dir2] = width; G.arcs[dir2][dir1] = width;
Edge[i].Head = s1;
Edge[i].Tail = s2;
Edge[i].lowcost = width;
}
}
// 使用冒泡排序算法对边值进行排序
/*按照升序进行排序*/
void Sort(AMGraph G) {
int m = G.arcnum - 2;
int flag = 1;
while (m > 0 && flag) {
flag = 0;
for (int i = 0; i <= m; i++) {
if (Edge[i].lowcost > Edge[i + 1].lowcost) {
flag = 1;
VerTexType temp1 = Edge[i].Head;
Edge[i].Head = Edge[i + 1].Head;
Edge[i + 1].Head = temp1;
VerTexType temp2 = Edge[i].Tail;
Edge[i].Tail = Edge[i + 1].Tail;
Edge[i + 1].Tail = temp2;
ArcType temparc = Edge[i].lowcost;
Edge[i].lowcost = Edge[i + 1].lowcost;
Edge[i + 1].lowcost = temparc;
}
}
m--;
}//while
}
int visited[MAXNUM];
void MinSpanTree_Kruskal(AMGraph G) {
Sort(G);
for (int i = 0; i < G.vexnum; i++) {
visited[i] = i;// 各边自成一连通分量
}
for (int i = 0; i < G.arcnum; i++) {
int v1, v2;
v1 = LocateVex(G, Edge[i].Head);
v2 = LocateVex(G, Edge[i].Tail);
int vs1, vs2; // 依次获取自成的连通分量
vs1 = visited[v1];
vs2 = visited[v2];
if (vs1 != vs2) {
//边的两个顶点属于不同的连通分量
cout << Edge[i].Head << " " << Edge[i].Tail << endl;// 输出此边
for (int j = 0; j < G.vexnum; j++) {
// 合并各个连通分量
if (visited[j] == vs2) {
visited[j] = vs1;
}
}
}
}
}
int main()
{
AMGraph G;
Create_AMGraph(G);
MinSpanTree_Kruskal(G);
char c;
cin >> c;
return 0;
}
