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

要求对一个图使用kruskal算法求最小生成树，依次输出选出的边所关联的顶点序列，要求下标较小者在前。

输入若干行整数
第一行为两个整数，分别为图的顶点数和边数
第二行开始是该图的邻接矩阵，主对角线统一用0表示，无直接路径的两点用100来表示（保证各边权值小于100）输出若干用空格隔开的整数

样例输入

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

 
思路：使用Kruskal求解即可

代码：

#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;
}