利用克鲁斯卡尔算法求最小生成树

时间：2025-04-22 21:56:21

思路:最小生成树即为无向连通图G的一个子图如果是一颗包含G的所有顶点且权最小的树则称为最小生成树。克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用的（所选的边不能构成回路）最小权值边。所以第一步是将所有边按照权值从小到大的顺序排序，接下来从小到大依次考察每一条边。具体实现过程如下：

<1>设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。

<2>在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。

<3>如此重复下去，直到所有顶点在同一连通分量上为止。

在上面的算法思路中，最为复杂的部分是连通分量的查询和合并，并查集这个数据结构可以方便快速的解决这个问题。基本的处理思想是：初始时把每个对象看作是一个单元素集合；然后依次按顺序读入联通边，将连通边中的两个元素合并。在此过程中将重复使用一个搜索（Find）运算，确定一个集合在那个集合中。当读入一个连通边（ｕ，ｖ）时，先判断ｕ和ｖ是否在同一个集合中，如果是则不用合并；如果不是，则用一个合并运算把ｕ、ｖ所在集合合并，使得这两个集合中的任意两个元素都连通。因此并查集在处理时，主要用到搜索和合并两个运算。为了方便并查集的描述与实现，通常把先后加入到一个集合中的元素表示成一个树结构，并用根结点的序号(在这里根节点的序号就是数组的下标值)来表示这个集合。因此定义一个parent[n]的数组，parent[i]中存放的就是结点ｉ+1所在的树中结点ｉ+1的父亲节点的序号。

#include<>
#include<>
#define MAXVEX 20
#define INF 32767
typedef struct
{
 int arcs[MAXVEX][MAXVEX];
 char vex[MAXVEX];
 int vexnum;
 int arcnum;
}AdjMatrix; //图 
typedef struct {
 int start;
 int end;
 int weight;
 int isUsed;
} Brim;  //边 
int LocateVex(AdjMatrix* G, char v);
void Create(AdjMatrix *G);
int Find(int *parent, int f);
void Kruskal(AdjMatrix *G)
int main()
{
 AdjMatrix* G = (AdjMatrix*)malloc(sizeof(AdjMatrix));
 Create(G);
 Kruskal(G);
 return 0;
}

int Find(int *parent, int f)
{
 //从下标f开始寻找parent数组中元素为0的下标
 int x;
 for(x = f;parent[x] > 0; x=parent[x]);
 return x;
}
void Create(AdjMatrix *G)
{
 int i, j, k;
 char vex1, vex2;
 int weight;
 scanf("%d%d", &G->vexnum, &G->arcnum);
 getchar();
 for (i = 0; i < G->vexnum; i++)
 {
  for (j = 0; j < G->vexnum; j++)
  {
   G->arcs[i][j] = INF;
  }
 }
 for (i = 0; i < G->vexnum; i++)
 {
  scanf("%c", &G->vex[i]); //输入各个顶点 
 }
 getchar();
 for (i = 0; i < G->arcnum; i++)
 {
  scanf("(%c,%c,%d)", &vex1, &vex2, &weight);  //输入边的信息 
  j = LocateVex(G, vex1);
  k = LocateVex(G, vex2);
  G->arcs[j][k] = weight;
  G->arcs[k][j] = weight;
 }
}

void Kruskal(AdjMatrix *G)
{
Brim brim[MAXVEX];
 int i, j;
 int k = 0;
 int n, m;
 for (i = 0; i < G->vexnum- 1; i++) {  //生成树最多只有n-1条边 
  for (j = i + 1; j < G->vexnum; j++) {
   if (G->arcs[i][j] != INF) {
    brim[k].start = i;
    brim[k].end = j;
    brim[k].weight = G->arcs[i][j];
    brim[k].isUsed = 0;
    k++;
   }
  }
 }
 for (i = 0; i < k - 1; i++)
 {
  for (j = i + 1; j < k; j++)
  {
   if (brim[i].weight > brim[j].weight)
   {
    Brim tmp = brim[i];
    brim[i] = brim[j];
    brim[j] = tmp;
   }
  }
 }
 int parent[MAXVEX] = { 0 };
 for (int i = 0; i < G->arcnum; i++)
 {
  n = Find(parent, brim[i].start);  //找到根节点 
  m = Find(parent, brim[i].end);    //找到根节点 
  if (n != m)//m=n说明有环
  {
   parent[n] = m;   //将根节点n所在的树作为m的子树  合并 
   brim[i].isUsed = 1;
  }
  printf("(%c,%c,%d,%d)", G->vex[brim[i].start], G->vex[brim[i].end], brim[i].weight, brim[i].isUsed);
 }
 }

相关文章