数据结构与算法（十三）——连通图的最小生成树问题

拉维

发布于 2022-06-15 11:51:46

3K0

发布于 2022-06-15 11:51:46

文章被收录于专栏：iOS小生活iOS小生活

一、最小生成树的定义介绍

1，连通图的生成树

一个连通图的生成树指的是，极小的连通子图，它含有图中的全部n个顶点，但是只足以构成一棵树的（n-1）条边。

一定要注意啊，生成树只是长得像树，它本质上不是树，它只是一个名词而已，它本质上是一个连通子图。

综上，构成连通图的生成树的三个基本要素是：

①图是连通的

②图中包含了全部N个顶点

③图中边的数量等于（N-1）条边

下面我们来看几个例子。

如图1所示，它不是一个连通图的生成树，因为它有8个顶点，但是有9条边。

如图2所示，所有顶点都是连通的，有8个顶点，有7条边，因此它是连通图的生成树。

如图3所示，它不是一个连通图的生成树，因为它有8个顶点，但是却有8条边。

如图4所示，虽然它有8个顶点7条边，但是它不是连通的，因此它不是连通图的生成树。

2，连通图的最小生成树

首先来看一个题目。

如上图所示，假设现在有N个顶点，每个顶点连接的路径是不一样的。请你设计一个算法，快速找出能覆盖所有顶点的路径。

实际上，上面👆这道题目就是在求连通图的最小生成树。我们可以将这道题目与实际场景结合一下，假设每个顶点都是一个村落，现在要为这些村落通网线，上图中的红色的权重值就是村落之间的距离，现在需要据此设计一个最小成本的网络布线线路。

我们现在请了两个设计师进行方案的设计，下面来依次看一下。

方案1：

该方案的路径值大小为：10+12+8+11+17+19+16+7=100。

方案2：

该方案的路径值大小是：11+10+12+8+16+19+16+7=99

可以看到，上面👆的俩方案都是连通图的生成树，但是方案2要比方案1的路径值要小，因此我们肯定是选择方案2，因为它的网络布线成本更小。

通过上面的例子，我们可以知道，连通图的最小生成树指的就是，连通图的所有生成树中路径最小的那一个生成树。

二、普里姆（Prim）算法

需要事先说明的一点是，我们这里采用邻接矩阵的方式来存储图结构。

1，算法思路：

该算法最精妙的地方就在于，它设计了两个数组weights和previousVertexes。

weights是一个数组，图有多少个顶点，weights数组就有多少个元素

weights[i]的取值有3种：0、权值、无穷大。

（1）当weights[i]==0的时候，代表顶点i已经放进最小生成树中了

（2）当weights[i]==权值的时候，代表顶点i与当前已经存在于连通图最小生成树中的各顶点连成的边中的权重最小的边的权重值

（3）当weights[i]==无穷大的时候，代表顶点i与当前已经存在于连通图生成树中的任何顶点都不存在连接关系

previousVertexes也是一个数组，图中有多少个顶点，previousVertexes数组就有多少元素

previousVertexes[i]的含义是：在最小生成树中，顶点i连接的上一个顶点。

最小生成树从顶点0开始，因此我们首先将顶点0放入到最小生成树中，此时设置weights[0] = 0；此时在最小生成树中，顶点0是没有上一个顶点的，因此将previousVertexes[0]设置为0。

由于weights是一个数组，它存储的是图中各个顶点分别与已存在于生成树中的各个顶点的连线的最小权重。此时生成树中只有一个顶点0，因此我们就从顶点1开始遍历图中所有的顶点，进而将顶点0与其他各个顶点的连接关系以及对应权重存储到weights数组中。

如果图有N个顶点，那么连通图的最小生成树就有（N-1）条边。到现在为止，最小生成树中只加入了一个顶点0，因此我们就可以遍历N-1次，每一次遍历就处理一个最小生成树的边，所以我们就从顶点1开始对图中的剩余顶点进行遍历。

在每一次遍历中，都要找到当前的weights数组中的最小权重值，由于当前的weights数组中存储的是通过生成树中的各个顶点所能抵达的尚未加入到最小生成树中的各个顶点的边的权重值，因此我们找到当前的weights数组中的最小权重值（比如是weights[k]）之后就能够找到对应的顶点k。

找到顶点k之后，我们将weights[k]设置为0，以标记顶点K已经存在于最小生成树中了。

现在最小生成树中已经新增了一个顶点K，所以我们还需要将顶点K的所有边信息（连接顶点）都放到weights数组中。当顶点K连接的某一个顶点（比如是顶点j还有其他的连接顶点的时候，那么就要比较这两条边的权重值的大小，保留权重值较小的那一个，也就是说，需要保留顶点j连接的已经存在于最小生成树中的各个顶点的权重最小的那一条边。现在已经通过weights[j]将顶点j与顶点k的这条边的权重值记录下来了，那么如何来记录顶点j与顶点k的这条边呢？答案是通过previousVertexes[j] = k来记录。

然后进入下一层循环，处理下一条边。

2，代码

//
//  main.c
//  连接图的最小生成树
//
//  Created by 拉维 on 2022/4/26.
//


#include <stdio.h>


#pragma mark - 创建一个图


// 无穷大
#define INFINITY 65535


// 图中顶点的最大数量
#define MaxVertexesCount 20


// 顶点值类型
typedef int VertexValueType;


// 图结构
typedef struct Graph {
  VertexValueType vertexes[MaxVertexesCount]; // 顶点表
  int edges[MaxVertexesCount][MaxVertexesCount]; // 边表
  int countOfVertexes; // 顶点数量
  int countOfEdges; // 边的数量
} Graph;


// 创建图
void createGraph(Graph *graph) {
  // 初始化顶点数和边数
  graph->countOfVertexes = 9;
  graph->countOfEdges = 15;

  // 初始化顶点值
  for (int i = 0; i < graph->countOfVertexes; i++) {
    graph->vertexes[i] = i;
  }

  // 初始化边表
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = 0; j < graph->countOfVertexes; j++) {
      graph->edges[i][j] = i==j ? 0 : INFINITY;
    }
  }

  // 个性化边表信息
  graph->edges[0][1]=10;
  graph->edges[0][5]=11;
  graph->edges[1][2]=18;
  graph->edges[1][8]=12;
  graph->edges[1][6]=16;
  graph->edges[2][8]=8;
  graph->edges[2][3]=22;
  graph->edges[3][8]=21;
  graph->edges[3][6]=24;
  graph->edges[3][7]=16;
  graph->edges[3][4]=20;
  graph->edges[4][7]=7;
  graph->edges[4][5]=26;
  graph->edges[5][6]=17;
  graph->edges[6][7]=19;

  // 由于是无向图，因此对称
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = i + 1; j < graph->countOfVertexes; j++) {
      graph->edges[j][i] = graph->edges[i][j];
    }
  }
}


#pragma mark - 连接图的最小生成树


void minSpanningTree(Graph graph) {
  int weights[graph.countOfVertexes];
  int previousVertexes[graph.countOfVertexes];

  // 1，将顶点0作为第一个顶点加入到最小生成树中
  // 1.1 将顶点0标记为已加入到最小生成树
  weights[0] = 0;
  // 1.2 顶点0在最小生成树中的上一个顶点就是其自身
  previousVertexes[0] = 0;

  // 1.3 遍历找到与顶点0连接的所有顶点，并将边的权值信息存到weights数组中
  for (int i = 1; i < graph.countOfVertexes; i++) {
    weights[i] = graph.edges[0][i];
    previousVertexes[i] = 0;
  }

  // 2，循环处理最小生成树中的各个边
  for (int i = 1; i < graph.countOfVertexes; i++) {
    // 2.1 找到weights数组中权重最小的那一个
    int minWeight = INFINITY;
    int minIndex = 0;
    for (int i = 0; i < graph.countOfVertexes; i++) {
      // 只查找那些尚未加入到最小生成树的顶点
      if (weights[i] != 0 && weights[i] < minWeight) {
        minWeight = weights[i];
        minIndex = i;
      }
    }

    // 2.2 打印当前找到的这条边信息
    printf("[%d, %d] = %d\n", previousVertexes[minIndex], minIndex, weights[minIndex]);

    // 2.3 将找到的权重最小的那一条边连接的顶点（顶点minIndex）加入到最小生成树中
    weights[minIndex] = 0;

    // 2.4 将顶点minIndex连接的其他顶点都加入到weights数组中
    for (int i = 0; i < graph.countOfVertexes; i++) {
      /*
       更新weights[i]有三个条件：
       ①顶点i尚未加入到最小生成树中
       ②顶点i与顶点minIndex有连接
       ③【顶点i与顶点minIndex的连接边的权重值】，比【顶点i与已经加入到最小生成树中的各个顶点的连接边的权重值】要小
       */
      if (weights[i]!=0 && graph.edges[minIndex][i] < weights[i]) {
        // 将顶点i连接的已经存在于最小生成树中的各个顶点的边的权重值最小的那一个更新到weights数组中
        weights[i] = graph.edges[minIndex][i];
        // 记录顶点i与已经存在于最小生成树中的哪一个顶点的连接权重是最小的
        previousVertexes[i] = minIndex;
      }
    }
  }
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);
  minSpanningTree(graph);

  return 0;
}

三、克鲁斯卡尔（Kruskal）算法

1，思路

（1）首先，将图的边表信息转换成边表结构数组，边表数组中的每一个元素中包含三个要素：该边的头顶点、该边的尾顶点、该边的权重。

（2）然后，按照权重值大小，对边表结构数组进行升序排列；

（3）声明并初始化rearVertexes数组，图有多少个顶点，该数组就有多少个顶点。

rearVertexes[i]有两个取值，其含义如下：

①取值为0，在当前的最小生成树中，顶点i后面已经没有其他可以连接的顶点了

②取值大于0，在当前的最小生成树中，通过顶点i后面能找到的与之相连的顶点。

（4）再然后，依次遍历边表结构数组，也就是说按照权重从小到大遍历图的每一条边。在每一次遍历当中都执行如下操作：

①查找当前遍历到的边的头顶点start所能连接的终端顶点startRear

②查找当前遍历到的边的尾顶点end所能连接的终端顶点endRear

③如果前述①②两步查找到的终端顶点相等，则说明start和end之前已经可以间接连接起来了，如果此时再将二者直接相连，则会导致闭环，也就是说当前遍历到的边与已经存在于最小生成树中的其他边形成了闭环，所以略过

④如果前述①②两步查找到的终端顶点不相等，则说明如果将start和end相连则不会构成闭环，也就是说当前遍历到的边与已经存在于最小生成树中的其他边不会形成闭环，因此此时设置rearVertexes[startRear] = endRear

（5）一定要注意哦！Kruskal算法利用到的一个大原则就是：不能形成闭环。

2，代码

//
//  main.c
//  Kruskal
//
//  Created by 拉维 on 2022/4/27.
//


#include <stdio.h>
#include <stdlib.h>


// 一、创建图


// 无穷大
#define INFINITY 65535


// 图中最大顶点数
#define Max_Vertexes_Count 20


// 图结构
typedef struct Graph {
  int vertexes[Max_Vertexes_Count]; // 顶点表
  int edges[Max_Vertexes_Count][Max_Vertexes_Count]; // 边表
  int countOfVertexes; // 顶点数量
  int countOfEdges; // 边数
} Graph;


// 创建图
void createGraph(Graph *graph) {
  // 初始化顶点数和边数
  graph->countOfVertexes = 9;
  graph->countOfEdges = 15;

  // 初始化顶点表
  for (int i = 0; i < graph->countOfVertexes; i++) {
    graph->vertexes[i] = i;
  }

  // 初始化边表信息
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = i; j < graph->countOfVertexes; j++) {
      graph->edges[i][j] = i == j ? 0 : INFINITY;
    }
  }

  // 输入个性化边表信息
  graph->edges[0][1]=10;
  graph->edges[0][5]=11;
  graph->edges[1][2]=18;
  graph->edges[1][8]=12;
  graph->edges[1][6]=16;
  graph->edges[2][8]=8;
  graph->edges[2][3]=22;
  graph->edges[3][8]=21;
  graph->edges[3][6]=24;
  graph->edges[3][7]=16;
  graph->edges[3][4]=20;
  graph->edges[4][7]=7;
  graph->edges[4][5]=26;
  graph->edges[5][6]=17;
  graph->edges[6][7]=19;

  // 无向边需要对称
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = i+1; j < graph->countOfVertexes; j++) {
      graph->edges[j][i] = graph->edges[i][j];
    }
  }
}


// 二、通过Kruskal算法来获取到连通图的最小生成树


// 边表信息结构
typedef struct EdgeNode {
  int start; // 边的头顶点的下标
  int end; // 边的尾结点的下标
  int weight; // 边的权重值
} EdgeNode;


// 查找顶点在最小生成树中的能连接到的最下面的顶点
int findRearVertex(int vertexIndex, int *rearVertexes) {
  int rearIndex = vertexIndex;
  while (rearVertexes[rearIndex] > 0) {
    rearIndex = rearVertexes[rearIndex];
  }
  return  rearIndex;
}


void minSpanningTree(Graph graph) {
  // 1，将图的邻接矩阵转换成边表数组
  EdgeNode edgeNodes[graph.countOfEdges];
  int edgeNodeIndex = 0;

  for (int i = 0; i < graph.countOfVertexes; i++) {
    for (int j = i+1; j < graph.countOfVertexes; j++) {
      if (graph.edges[i][j] < INFINITY) {
        struct EdgeNode *edgeNode = malloc(sizeof(EdgeNode));
        edgeNode->start = i;
        edgeNode->end = j;
        edgeNode->weight = graph.edges[i][j];
        edgeNodes[edgeNodeIndex++] = *edgeNode;
      }
    }
  }

  // 2，对边表数组按照边的权重升序排序
  for (int i = 0; i < graph.countOfEdges; i++) {
    for (int j = i+1; j < graph.countOfEdges; j++) {
      if (edgeNodes[i].weight > edgeNodes[j].weight) {
        EdgeNode tempNode = edgeNodes[i];
        edgeNodes[i] = edgeNodes[j];
        edgeNodes[j] = tempNode;
      }
    }
  }

  // 3，声明并初始化rearVertexes数组，记录对应顶点在最小生成树中所能连接到的最尾端的顶点
  /*
   rearVertexes主要用来判断两顶点是否会产生闭环
   */
  int rearVertexes[graph.countOfVertexes];
  for (int i = 0; i < graph.countOfVertexes; i++) {
    rearVertexes[i] = 0; // 值为0代表该顶点下面没有与之连接的其他顶点了
  }

  // 4，遍历所有的边表信息
  for (int i = 0; i < graph.countOfEdges; i++) {
    // 查询当前这条边是否在最小生成树中构成闭环
    EdgeNode edgeNode = edgeNodes[i];
    int rearVertexFromStart = findRearVertex(edgeNode.start, rearVertexes);
    int rearVertexFromEnd = findRearVertex(edgeNode.end, rearVertexes);
    if (rearVertexFromStart != rearVertexFromEnd) {
      // 不构成闭环的话，那么就将该边加入进最小生成树中来
      rearVertexes[rearVertexFromStart] = rearVertexFromEnd; // ⚠️这里不太理解，这里是重点哦！

      // 打印边信息
      printf("[%d,%d]=%d\n", edgeNode.start, edgeNode.end, edgeNode.weight);
    }
  }
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);
  minSpanningTree(graph);

  return 0;
}

3，流程分析

首先来复习一下题目，如下图所示，左侧是一个网（带有权重的图），右侧是改造后的边表数组：

在第一层遍历中，遍历到的是最小的那一条边：V4—V7，此时start=4，end=7，经计算后得到rearVertexFromStart=4，rearVertexFromEnd=7，可以看出rearVertexFromStart!=rearVertexFromEnd，所以此时设置rearVertexes[4] = 7，代表在当前的最小生成树中可以通过顶点4找到顶点7。

注意，上述分析中的start、end分别对应下图中的begin、end，rearVertexFromStart、rearVertexFromEnd分别对应下图中的n、m，rearVertexes数组对应下图中的parent数组。