# 【MST】kruskal算法求最小生成树

6 10
0 6 1 5 100 100
6 0 5 100 3 100
1 5 0 5 6 4
5 100 5 0 100 2
100 3 6 100 0 6
100 100 4 2 6 0

1 3 4 6 2 5 3 6 2 3

#include<iostream>
#include<malloc.h>
#include<queue>
#include <algorithm>
#include<functional>
using namespace std;

#define maxNum 100 //定义邻接矩阵的最大定点数
#define maxWeight 100 //边权最大值
int visited[maxNum][maxNum];//用来表示边visited[i][j]是否被访问过，初始化都是0
int pre[maxNum];
//int Find(int x) { return (x == pre[x] ? x : pre[x] = Find(pre[x])); }//并查集查祖先
int Find(int x)
{
int r = x;
while (r != pre[r])
r = pre[r];
int i = x, j;
while (pre[i] != r)//路径优化
{
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
void mix(int x, int y)
{
int fx = Find(x), fy = Find(y);
if (fx != fy)
{
pre[fy] = fx;
}
}
//顶点信息
typedef struct
{
int id;
int dist;
}node;
//图的邻接矩阵表示结构
typedef struct
{
node v[maxNum];
int e[maxNum][maxNum];//图的顶点信息
int vNum;//顶点个数
int eNum;//边的个数
}graph;
//函数声明
void createGraph(graph *g);//创建图g
void kruskal(graph *g);
void createGraph(graph *g)//创建图g
{
//cout << "请输入顶点个数vNum:\n";
cin >> g->vNum;
cin >> g->eNum;
int i, j;
//cout << "输入邻接矩阵权值：" << endl;
for (i = 1; i <= g->vNum; i++)
for (j = 1; j <= g->vNum; j++)
{
cin >> g->e[i][j];
if (g->e[i][j] == maxNum)
g->e[i][j] = maxNum;
}
}
void kruskal(graph *g)
{
//cout << "最小生成树是：" << endl;
int k = 1;
int i, j;
int a = 1, b = 1;
int min = g->e[a][b];
//初始化visited[][]
for (i = 1; i <= g->vNum; i++)
for (j = 1; j <= g->vNum; j++)
{
visited[i][j] = 0;//表示边i-j没有被访问过
}
for (i = 1; i <= g->vNum; i++)//初始化并查集
{
pre[i] = i;
}
while (k <= g->vNum - 1)
{
//找出最小边i->j
for (i = 1; i <= g->vNum; i++)
for (j = 1; j <= g->vNum; j++)
{
if (g->e[i][j] < min && visited[i][j] == 0)
{
min = g->e[i][j];
a = i;
b = j;
}
}
visited[a][b] = 1;
visited[b][a] = 1;
min = maxWeight;
if (Find(a) != Find(b))//a b不在一个连通分量中，则合并
{
//cout << a << "->" << b << endl;
if (a<=b)
{
cout << a << " " << b << " ";
}
else cout << b << " " << a << " ";
mix(a, b);
k++;
}
}
}

int main()
{
graph *g = new graph;
createGraph(g);
kruskal(g);
cout << endl;
return 0;
}