12.4 Borüvka算法

文章目录

• 算法过程及举例
• Python
• 本文案例Python测试代码

算法过程及举例

  Borüvka算法是利用组件/分量component的概念来组建最小生成树的。算法和Kruskal算法一样需要用到并查集。算法和Kruskal不同的是，Kruskal算法不断地连接点，而Buruvka算法不断去连接组件。
  本来不想写Borüvka算法，这个算法1926年就被发明出来了，这个时候还没有计算机呢。讲道理后面发明的算法肯定比这个算法先进，但是随着时代的发展，有人发现了Borüvka算法特有的并行计算优势。
  我还是以那个例子讲述算法过程，首先是这张图：

  每个组件的点我都用相同颜色去标记。首先是合并AB，形成了六个组件：

  然后是CF,于是组件数量又减少到了5个：

  以D为起始点，再继续找到组件边界最小边为2，合并后组件为4个：

  再以E为中心去寻找，找到了EF，此时为三个组件：

  以G为中心，找到最小为FG，组件剩下两个：

  再进行一轮。以AB为组件，找到最小的为AC：

  具体的算法是遍历点时，将最小权重边、最小权重按组件进行分组，具体分组技术可以使用并查集的编号来进行分组。由于合并的时候会使并查集发生变化，所以必须再进行一次并查集检查。

Python

  上次算法思想的python实现如下：

# _*_ coding:utf-8


# 并查集
class Handler:

    def __init__(self, vertex):
        self.__vertex = vertex
        self.__parent = self
        self.__rank = 0

    def union(self, other):
        if self.__rank > other.__rank:
            other.__parent = self
        else:
            self.__parent = other
            if self.__rank == other.__rank:
                other.__rank = other.__rank + 1

    def find(self):
        x = self
        if x != x.__parent:
            x.__parent = x.__parent.find()
        return x.__parent

    @property
    def vertex(self):
        return self.__vertex


class DisjointSet:
    # 对于每一个item，应该找到属于它的最小的集合
    def __init__(self, n):
        self.__forest = [None] * n
        self.__count = 0

    def make_set(self, item):
        h = Handler(item)
        self.__forest[item] = h
        self.__count += 1
        return h

    def union_set(self, x, y):
        self.find_set(x).union(self.find_set(y))
        self.__count -= 1

    def find_set(self, item):
        return self.__forest[item].find()

    @property
    def count(self):
        return self.__count


# 并查集弄完就是图

class Edge:

    def __init__(self, to, weight):
        self.__to = to
        self.__weight = weight

    @property
    def to(self):
        return self.__to

    @property
    def weight(self):
        return self.__weight


class WeightedGraph:
    def __init__(self, vertices, edges, pos, colors):
        self.__vertices = vertices
        self.__edges = edges
        # 用于图形化
        self.__pos = pos
        self.__colors = colors

    @property
    def vertices(self):
        return self.__vertices

    @property
    def edges(self):
        return self.__edges

    def boruvka(self):
        # 初始化并查集，每个点是一个并查集
        # 初始化生成树
        st = [[] for _ in self.__vertices]
        n = len(self.__vertices)
        # 初始化并查集
        s = DisjointSet(n)
        for i in range(n):
            s.make_set(i)

        # 复制边的列表
        all_edges = [edges[:] for edges in self.__edges]
        # 组件数量
        while s.count > 1:
            # 找到组件的最小权重边
            # 先找到一个组件
            components = []
            min_weights = [None] * n
            min_edges = [None] * n
            min_from_vertices = [None] * n
            for v in range(n):
                component = s.find_set(v).vertex
                for edge in all_edges[v]:
                    if min_weights[component] is None or edge.weight < min_weights[component]:
                        min_weights[component] = edge.weight
                        min_edges[component] = edge
                        min_from_vertices[component] = v
            # 并查集合并
            for component, min_edge in enumerate(min_edges):
                if min_edge is not None:
                    v = min_from_vertices[component]
                    # 删除边
                    all_edges[min_from_vertices[component]].remove(min_edge)
                    u = min_edge.to
                    # 二次校验
                    if s.find_set(u) != s.find_set(v):
                        s.union_set(u, v)
                        st[v].append(min_edge)
                        st[u].append(Edge(v, min_weights[component]))
                        print(f"剩余{s.count}个组件", self.to_boruvka_dot(st, s))
        return st

    def to_dot(self):
        dot_s = 'graph s {\n\tlayout=fdp\n'
        for i, v in enumerate(self.__vertices):
            dot_s += f'\t"{v}"[pos="{self.__pos[i]}"];\n'
        for i, e in enumerate(self.__edges):
            for t in e:
                if t.to < i:
                    continue
                dot_s += f'\t\"{self.__vertices[i]}\"--"{self.__vertices[t.to]}"[label="{t.weight}"];\n'
        dot_s += '}\n'
        return dot_s

    def to_boruvka_dot(self, a, ds):
        dot_s = 'graph s {\n\tlayout=fdp\n'
        for i, v in enumerate(self.__vertices):
            dot_s += f'\t"{v}"[pos="{self.__pos[i]}";'
            dot_s += f'style=filled;fillcolor={self.__colors[ds.find_set(i).vertex]};'
            dot_s += '];\n'
        for i, e in enumerate(self.__edges):
            for t in e:
                if t.to < i:
                    continue
                dot_s += f'\t\"{self.__vertices[i]}\"--"{self.__vertices[t.to]}"[label="{t.weight}";'
                for st_edge in a[i]:
                    if st_edge.to == t.to:
                        dot_s += 'color=red;'
                dot_s += '];\n'
        dot_s += '}\n'
        return dot_s

本文案例Python测试代码

import unittest

from com.youngthing.graph.boruvka import Edge
from com.youngthing.graph.boruvka import WeightedGraph


class PrimMstTestCase(unittest.TestCase):
    def test_prim(self):
        # 做一张图
        vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', ]
        # 设计容量
        edges = [
            [Edge(1, 4), Edge(2, 8), ],  # a
            [Edge(0, 4), Edge(2, 9), Edge(3, 8), Edge(4, 10)],  # B
            [Edge(0, 8), Edge(1, 9), Edge(3, 2), Edge(5, 1)],  # C
            [Edge(1, 8), Edge(2, 2), Edge(4, 7), Edge(5, 9)],  # D
            [Edge(1, 10), Edge(3, 7), Edge(5, 5), Edge(6, 6)],  # E
            [Edge(2, 1), Edge(3, 9), Edge(4, 5), Edge(6, 2)],  # f
            [Edge(4, 6), Edge(5, 2)],  # g
        ]
        pos = ["0,0!", "2,1!", "2,-1!", "4,0!", "6,1!", "6,-1!", "8,0!", ]
        colors = ["red", "orange", "yellow", "green", "cyan", "blue", "purple", ]
        fn = WeightedGraph(vertices, edges, pos, colors)

        print(fn.to_dot())

        tree = fn.boruvka()
        print(WeightedGraph(vertices, tree, pos, colors).to_dot())


if __name__ == '__main__':
    unittest.main()