Python 实现Kruskal算法

可以使用Kruskal算法找到带权无向图的最小生成树。在所有可能的生成树中，最小生成树是一个跨越图中的每个顶点并具有最低总权重的生成树。

该算法的工作原理是将图的所有边按其权重递增的顺序进行排序，然后逐个将边添加到最小生成树中，如果添加边不会创建循环，则将该边添加到最小生成树中。这样做直到所有顶点都被连接。

Kruskal算法的步骤

以下是Kruskal算法的步骤：

将图的所有边按其权重递增的顺序进行排序。
创建一个新的空集表示最小生成树。
遍历排序后的边列表中的每个边缘。
检查是否将边添加到最小生成树中会创建循环。如果不是，则将边添加到最小生成树中。重复此操作，直到连接每个顶点。

Kruskal算法的时间复杂度为O（E log E），其中E是图中的边数。这使得它成为了发现大型图的最小生成树的非常有效的算法。

在Python中实现Kruskal算法

逐步实现如下：

我们定义一个Graph类，其中有三个实例变量：vertices是图中所有顶点的列表；edges是图中所有边的列表；而adjacency_list是表示图的邻接列表的字典。
我们定义一个 add_edge 方法来添加一条边到图中。此方法接受三个参数：u和v是边连接的顶点；而weight是边的权重。我们将边添加到边列表中，并将其添加到adjacency_list中。
我们定义一个方法find_parent，以在不相交集数据结构中查找给定顶点i的父项。使用不相交集数据结构跟踪图的连接元素。每个顶点最初都是自己的父项，我们使用find_parent方法查找属于i的联通分量的根。
我们定义了一个合并两个不相交集中的连接分量的方法并将其称为union。 union方法有四个参数：parent是表示每个顶点的父项的字典；rank是表示每个顶点的等级的字典；x和y是我们想要合并的连接分量的顶点。我们使用find_parent方法找到 x 和 y 属于的连接分量的根，然后基于它们的等级合并这些分量。
我们定义了Kruskal方法来实现Kruskal算法。该方法初始化了一个空集minimum_spanning_tree来存储最小生成树中的边缘。它还为不相交集初始化了一个父项字典和等级字典。

代码：

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.edges = []
        self.adjacency_list = {v: [] for v in vertices}

    def add_edge(self, u, v, weight):
        self.edges.append((u, v, weight))
        self.adjacency_list[u].append((v, weight))
        self.adjacency_list[v].append((u, weight))

    def find_parent(self, parent, i):
        if parent[i] == i:
            return i
        return self.find_parent(parent, parent[i])

    def union(self, parent, rank, x, y):
        root_x = self.find_parent(parent, x)
        root_y = self.find_parent(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    def kruskal(self):
        minimum_spanning_tree = set()
        parent = {}
        rank = {}
        for v in self.vertices:
            parent[v] = v
            rank[v] = 0
        sorted_edges = sorted(self.edges, key=lambda x: x[2])
        for edge in sorted_edges:
            u, v, weight = edge
            root_u = self.find_parent(parent, u)
            root_v = self.find_parent(parent, v)
            if root_u != root_v:
                minimum_spanning_tree.add(edge)
                self.union(parent, rank, root_u, root_v)
        return minimum_spanning_tree
vertices = [0, 1, 2, 3]
g = Graph(vertices)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 10)
g.add_edge(0, 3, 3)
g.add_edge(1, 3, 1)
g.add_edge(2, 3, 4)
minimum_spanning_tree = g.kruskal()
print(minimum_spanning_tree)

输出：

{(1, 3, 1), (2, 3, 4), (0, 3, 3)}

输入的图如下所示：

Implementation of Kruskal's Algorithm in Python

Kruskal算法是一种用于找到连通带权图的最小生成树的贪心算法。

上述集合表示输入图的最小生成树中的边。我们可以看到最小生成树的总权值为 1+3+5=9。

该算法通过按权重对图的边进行排序，然后从最小权重开始逐个将边添加到最小生成树中。
每次添加边到最小生成树后，都会检查该边是否会形成一个环。如果边连接的两个顶点已经在同一个连通分量中，则添加该边会形成一个环，该边将被舍弃。
只要图是连通的并且边的权重是不同的，Kruskal算法就能始终识别图的最小生成树。
Kruskal算法的时间复杂度为 O(E log E)，其中 E 是图中的边数。因为该算法需要按权重对边进行排序，这需要O(E log E)的时间，然后再逐个处理每个边，这需要O(E)的时间。
Kruskal算法的空间复杂度为 O(V + E)，其中 V 是图中的顶点数，E 是图中的边数。因为该算法需要存储边和图的邻接列表，以及用于跟踪连通分量的不相交的集数据结构。
Kruskal算法可以使用优先队列更加高效地按权重对边进行排序。这将改善算法的时间复杂度为O(E log V)，其中V是图的顶点数。但是，空间复杂度仍然是O(V + E)。
在某些情况下，给定图可能有多个最小生成树。Kruskal算法将找到其中一棵树，但不一定是所有树。
Kruskal算法常用于网络设计问题，例如设计通信网络或电力网。该算法还可以使用Python中的优先队列来实现：

代码:

import queue
class Graph:
     def __init__(self, vertices):
         self.vertices = vertices
         self.edges = []
         self.parent = {}
         self.rank = {}

         for v in self.vertices:
             self.make_set(v)

     def add_edge(self, u, v, w):
         self.edges.append((w, u, v))

     def make_set(self, v):
         self.parent[v] = v
         self.rank[v] = 0

     def find(self, v):
         if self.parent[v] != v:
             self.parent[v] = self.find(self.parent[v])
         return self.parent[v]

     def union(self, u, v):
         root1 = self.find(u)
         root2 = self.find(v)

         if root1 != root2:
             if self.rank[root1] > self.rank[root2]:
                 self.parent[root2] = root1
             else:
                 self.parent[root1] = root2
                 if self.rank[root1] == self.rank[root2]:
                     self.rank[root2] += 1

     def kruskal(self):
         minimum_spanning_tree = set()

         # Sort edges by weight using priority queue
         edge_queue = queue.PriorityQueue()
         for edge in self.edges:
             edge_queue.put(edge)

         # Iterate through edges in priority queue and add to MST
         while not edge_queue.empty():
             weight, u, v = edge_queue.get()

             if self.find(u) != self.find(v):
                 self.union(u, v)
                 minimum_spanning_tree.add((u, v, weight))

         return minimum_spanning_tree
# Create a graph with 5 vertices
g = Graph([0, 1, 2, 3, 4])

# Add edges to the graph
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 3)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 5)
g.add_edge(1, 4, 3)
g.add_edge(2, 3, 1)
g.add_edge(2, 4, 4)
g.add_edge(3, 4, 5)

# Find the minimum spanning tree
mst = g.kruskal()

# Print the edges in the minimum spanning tree
for edge in mst:
     print(edge)

输出:

(2, 3, 1)
(0, 2, 3)
(0, 1, 2)
(1, 4, 3)

这些是上述图的最小生成树中的边。

在这个实现中，我们使用一个优先队列来根据权重排序边。我们将每个边添加到优先队列中，其权重作为优先级，这样当我们从队列中检索边时，我们总是首先获得具有最小权重的边。之后，我们通过遍历优先队列中的边，并将它们按顺序添加到最小生成树中，只要它们不会创建一个循环。我们使用不相交集数据结构的find和union方法来跟踪图的连通分量，就像之前的实现一样。

要使用此实现，您将创建一个Graph对象，使用add_edge方法添加边，然后调用kruskal方法来查找最小生成树。