数据结构和算法-最小生成树

一、概念

最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

生成树的特点：
1、图是连通图;
2、图中包含了了N个顶点;
3、图中边的数量等于N-1条边.

求最小生成树的算法有prim(普里姆)算法和kruskal(克鲁斯卡尔)算法

二、prim(普里姆)算法

1、思路

定义2个数组; adjvex ⽤来保存相关顶点下标; lowcost 保存顶点之间的权值
初始化2个数组, 从v0开始寻找最⼩⽣成树, 默认v0是最⼩⽣成树上第⼀个顶点
循环lowcost 数组,根据权值,找到顶点 k;
更新lowcost 数组
循环所有顶点,找到与顶点k 有关系的顶点. 并更新lowcost 数组与adjvex 数组;
2、代码实现

void MiniSpanTree_Prim(MGraph G){
    int min;
    int sum = 0;

    int adjvex[MAXVEX];//保存相关顶点下标，如顶点0和顶点相连，则adjvex[1] = 0;
    int lowcost[MAXVEX];//保存相关顶点的权值
    
    //当v0加入生成树，adjvex和lowcost数组的值初始化
    for (int i = 0; i<G.numNodes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }
    
    //循环除0以外的全部顶点，找到lowcost数组中最小的顶点k
    for (int i = 1; i<G.numNodes; i++) {
        min = INFINITYC;
        int j = 1;
        int k = 0;
        while (j<G.numNodes) {
            if (lowcost[j] != 0 && lowcost[j]<min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("v%d - v%d = %d\n",adjvex[k],k,G.arc[adjvex[k]][k]);
        sum += G.arc[adjvex[k]][k];
        lowcost[k] = 0; //顶点k已加入生成树
        
        //更新lowcost数组和adjvex数组
        for (j = 1; j<G.numNodes; j++) {
            if (lowcost[j] != 0 && G.arc[k][j]<lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

三、kruskal(克鲁斯卡尔)算法

1、思路

将邻接矩阵转化成边表数组;
对边表数组根据权值按照从⼩到⼤的顺序排序;
遍历所有的边, 通过parent 数组找到边的连接信息; 避免闭环问题;
如果不存在闭环问题,则加⼊到最⼩⽣成树中. 并且修改parent 数组

2、代码实现

边表数组Edge结构的定义

typedef struct
{
  int begin;
  int end;
  int weight;
}Edge;

根据权值进行排序

void sort(Edge edges[],MGraph G)
{
  //对权值进行排序(从小到大)
  int i, j;
  Edge temp;
  for ( i = 0; i < G.numEdges; i++)
  {
      for ( j = i + 1; j < G.numEdges; j++)
      {
          if (edges[i].weight > edges[j].weight)
          {
              temp = edges[i];
              edges[i] = edges[j];
              edges[j] = temp;
          }
      }
  }
  
  printf("边集数组根据权值排序之后的为:\n");
  for (i = 0; i < G.numEdges; i++)
  {
      printf("v%d - v%d = %d\n", edges[i].begin, edges[i].end, edges[i].weight);
  }
}

根据顶点f以及parent数组,可以找到当前顶点的尾部下标; 帮助我们判断两点之间是否存在闭环问题

int Find(int *parent, int f)
{
  while ( parent[f] > 0)
  {
      f = parent[f];
  }
  return f;
}

kruskal算法

void MiniSpanTree_Kruskal(MGraph G){
  int sum = 0;
  /* 定义一数组用来判断边与边是否形成环路,用来记录顶点间的连接关系. 通过它来防止最小生成树产生闭环;*/
  int parent[MAXVEX];
  //边表数组
  Edge edges[MAXVEX];
  int k = 0;
  //根据邻接矩阵生成边表数组
  for (int i = 0; i<G.numNodes; i++) {
      for (int j = i+1; j<G.numNodes; j++) {
          if (G.arc[i][j]<INFINITYC) {
              edges[k].begin = i;
              edges[k].end = j;
              edges[k].weight = G.arc[i][j];
              k++;
          }
      }
  }
  
  //将边表数组排序
  sort(edges, G);
  
  //初始化parent 值为0
  for (int i = 0; i<MAXVEX; i++) {
      parent[i] = 0;
  }
  int n,m;
  for (int i = 0; i<G.numEdges; i++) {
      n = Find(parent, edges[i].begin);
      m = Find(parent, edges[i].end);
      if (n != m) {
          parent[n] = m; //更新parent数组
          //非闭环情况下，且根据权值从小到大的排序边表数组，此时的边i是没有加入到生成树的最小边
          sum  += edges[i].weight; //边i加入的生成树
      }
  }
  printf("sum = %d\n",sum);
}