数据结构(16)-图之最小生成树

构造连通网的最小代价生成树称为最小生成树，也是一个图的极小连通子图，包含原图的所有顶点，且所有边的权值之和最小。

由于图的极小连通子图不一定是闭环的，而是一个树形结构，所以我们将其称为最小生成树。同一个图的最小生成树是不唯一的。

找到最小生成树，有两种经典的算法，普里姆算法和克鲁斯卡尔算法。

普里姆算法`(Prim)`

普里姆算法是以图的顶点为基础，从一个初始顶点开始，找到其他顶点权值最小的边，并把该顶点加入到已知顶点的集合中。当全部顶点都加入到集合时就完成了。普里姆算法的本质，是基于贪心算法。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

下面我们结合一个例子来看看普里姆算法，在下图中找出最小生成树：

prim示例.png

首先，我们选择一个顶点 $v_0$ ，然后从这个顶点开始，此时，我们只能选择去 $v_1$ 和 $v_5$ ，由于11>10，所以我们选择去 $v_1$ 。
从 $v_1$ 出发，我们可以选择去 $v_2$ 、 $v_8$ 、 $v_6$ 、 $v_5$ ，由于去 $v_5$ 的权值11最小，我们选择去 $v_5$ 。
从 $v_5$ 出发，我们可以选择去 $v_2$ 、 $v_8$ 、 $v_6$ 、 $v_4$ ，去 $v_8$ 的权值12最小，我们选择去 $v_8$ 。
以此类推，即可得到最小生成树。
需要注意的是我们每次找的路径点并不是当前顶点的邻接点，而是当前顶点能到的顶点。

首先我们需要生成一个数组来装我们保存的顶点在顶点组中的下标，还需要生成一个数组来保存顶点之间的权值用以比较权值的大小进而选择权值最小的路径。代码实现如下：

void primMinTree(MGraph graph) {
    // 存储已经加入最小生成树的顶点
    int adj[MAX_VEX_COUNT];
    // 存储当前顶点对应权值 当某一个顶点被加入最小生成树 就把其对应值置为0 便于区分
    int adjWeights[MAX_VEX_COUNT];
    // 最小生成树权值之和
    int sum = 0;
    
    // 先假定一个顶点作为起点
    adj[0] = 0;
    adjWeights[0] = 0;
    for (int i = 1; i < graph.vertexNum; i++) {
        adj[i] = 0;
        adjWeights[i] = graph.arc[0][i];
    }
    
    // 记录每一次遍历的最小权值
    int min = 0;
    for (int i = 1; i < graph.vertexNum; i++) {
        min = INT_INFINITY;
        int minIndex = 0;
        for (int j = 0; j < graph.vertexNum; j++) {
            // 找到当前顶点对应的权值列表中最小权值 及其对应的下标
            if (adjWeights[j] != 0 && min > adjWeights[j]) {
                min = adjWeights[j];
                minIndex = j;
            }
        }
        
        sum += min;
        
        printf("(V%d, V%d)=%d\n", adj[minIndex], minIndex, min);
        
        // 将当前顶点对应的下标设置为0 用以判断某个顶点是否已经被我们选中，即加入了adj数组
        adjWeights[minIndex] = 0;
        
        
        // 更新下一个结点对应的权值列表
        // 遍历邻接矩阵minIndex这一行的权值
        for (int j = 1; j < graph.vertexNum; j++) {
            if (adjWeights[j] != 0 && graph.arc[minIndex][j] < adjWeights[j]) {
                adjWeights[j] = graph.arc[minIndex][j];
                adj[j] = minIndex;
            }
        }
    }
    
    printf("\n==%d==\n", sum);
}

// 输出结果如下：
(V0, V1)=10
(V0, V5)=11
(V1, V8)=12
(V8, V2)=8
(V1, V6)=16
(V6, V7)=19
(V7, V4)=7
(V7, V3)=16

==99==

由代码可以看出， $m$ 各结点， $n$ 条边，普里姆算法的时间复杂度为 $O(n^2)$ ，其更适合解决边的绸密度更高的连通网。

克鲁斯卡尔算法`(Kruskal)`

普里姆算法是以顶点为起点，克鲁斯卡尔算法则是以边为目标构建，因为权值在边上，我们可以直接去找最小权值的边来构建生成树，但是这样需要注意的是防止边形成环。

使用克鲁斯卡尔算法，我们就需要用到图的存储结构中的边集数组结构：

typedef struct {
    // 边起点(默认为下标小的一头)顶点下标
    int begin;
    // 边终点(默认为下标大的一头)顶点下标
    int end;
    int weight;
} EdgeSet;

下面我们使用上述例子来看看克鲁斯卡尔算法的计算规则：

kruskal示例.png

void swapEdgeSet(EdgeSet *edges,int i, int j) {
    int tempValue;
    
    //交换edges[i].begin 和 edges[j].begin 的值
    tempValue = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = tempValue;
    
    //交换edges[i].end 和 edges[j].end 的值
    tempValue = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = tempValue;
    
    //交换edges[i].weight 和 edges[j].weight 的值
    tempValue = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = tempValue;
}

int partition(EdgeSet edges[], int startIndex, int endIndex) {
    // 先把一个位置的元素设置为基准元素
    int standardWeight = edges[startIndex].weight;
    int left = startIndex;
    int right = endIndex;
    
    while (left != right) {
        // 控制right指针比较并左移
        while (left < right && edges[right].weight > standardWeight) {
            right -= 1;
        }
        
        // 控制left指针比较并右移
        while (left < right && edges[left].weight <= standardWeight) {
            left += 1;
        }
        
        if (left < right) {
            swapEdgeSet(edges, left, right);
        }
    }
    
    swapEdgeSet(edges, left, startIndex);
    return left;
}

void quickSort(EdgeSet edges[], int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    
    // 找到基准元素的下标
    int standardIndex = partition(edges, startIndex, endIndex);
    quickSort(edges, startIndex, standardIndex - 1);
    quickSort(edges, standardIndex + 1, endIndex);
}

// 根据顶点f 和 parent数组找到当前顶点的尾部下标; 帮助我们判断2点之间是否存在闭环问题;
int find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void kruskalMinTree(MGraph graph) {
    
    EdgeSet edges[MAX_VEX_COUNT];
    // 边集数组中 起始下标比结束下标小
    
    int edgeLen = 0;
    for (int i = 0; i < graph.vertexNum - 1; i++) {
        for (int j = i+1; j < graph.vertexNum; j++) {
            if (graph.arc[i][j] < INT_INFINITY) {
                edges[edgeLen].begin = i;
                edges[edgeLen].end = j;
                edges[edgeLen].weight = graph.arc[i][j];
                edgeLen += 1;
            }
        }
    }
   
    quickSort(edges, 0, graph.edageNum - 1);
//    printf("排序后\n");
//    for (int i = 0; i < graph.edageNum; i++) {
//        printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
//    }
    
    
    int sum = 0;
    // 引入一个辅助数组判断是否形成闭环
    int parent[MAX_VEX_COUNT] = {0};
    for (int i = 0; i < graph.edageNum; i++) {
        int b = find(parent, edges[i].begin);
        int e = find(parent, edges[i].end);
        
        // 如果b == e说明形成了闭环 
        // b != e说明该路径不会形成闭环 我们可以使用 
        if (b != e) {
            parent[b] = e;
            printf("(V%d, V%d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
            sum += edges[i].weight;
        }
    }
    
    printf("==%d==", sum);
}

// 控制台输出
(V4, V7) 7
(V2, V8) 8
(V0, V1) 10
(V0, V5) 11
(V1, V8) 12
(V3, V7) 16
(V1, V6) 16
(V6, V7) 19
==99==

由代码可以看出， $m$ 各结点， $n$ 条边，克鲁斯卡尔算法的时间复杂度为find的时间复杂度由变数 $n$ 确定为 $O(loge)$ ，外层还有一个循环，加起来为 $O(e*loge)$ ，其更适合于求边稀疏的网的最小生成树。

参考文献：

大话数据结构

数据结构(16)-图之最小生成树

普里姆算法(Prim)

克鲁斯卡尔算法(Kruskal)

普里姆算法`(Prim)`

克鲁斯卡尔算法`(Kruskal)`