Kruskal 算法：测试新边是否创建圆

Question

我正在尝试在 Python 3.7 中实现 kruskal 算法。

所以我写了一个程序 "bfs" 来进行广度优先搜索，我想用它来检查添加到 kruskal 算法中的最小生成树的边不会创建一个圆。

from collections import deque #we import a queue structure
def bfs(G, startnode, endnode=None):
 B = {startnode}
 Q = deque([startnode])
 L = []
 while Q:
     v = Q.pop()
     L.append(v)
     #If a final node was specified we will end the search there (including the final node)
     if v == endnode:
         break
     for neighbor in G.neighbors(v):
         if not neighbor in B:
             B.add(neighbor)
             Q.appendleft(neighbor)
 return L

上面的代码应该是正确的，为了完整起见贴出来。接下来我们有kruskal的算法实现：

import networkx as nx 
def kruskal_bfs(G):
V =nx.Graph()
edges=sorted(G.edges(data=True), key=lambda t: t[2].get('weight', 1)) #sorts the edges (from Whosebug)
E_F = set([]) #mimimum spanning tree

for edge in edges:
    E_F.add((edge[0],edge[1])) #add edge to the mimumum spanning tree
    V.add_edges_from(list(E_F)) #combine it with the nodes for bfs
    startnode = edge[0]
    if bfs(V,startnode) == bfs(V, ):
        E_F.remove(edge)
    V.remove_edges_from(list(V.edges())) #reset edges of V
return E_F

我有 if bfs(V,startnode) == bfs(V, ): 的部分是我有点卡住的地方，如果有条件，我该如何完成这个。我尝试扩展 bfs 以包含某种形式的 "circle detection"。但是那没有用。

Answer 1

不是添加边并检查圆，而是在添加边之前比较树，并且仅在顶点未连接时添加它。此外，使用 UNION-FIND 会更有效率。

Kruskal 算法：测试新边是否创建圆

Kruskal's algorithm: test if new edge creates a circle

graph-theory

discrete-mathematics

graph-algorithm

kruskals-algorithm