Kruskal's algorithm: check circle free

Question

I hope mathstackexchange is the right place to ask this. I'm trying to implement kruskal's algorithm in Python 3.7.

So I wrote a programm "bfs" to do breadth first search which I want to use to check that the edges that are added to the minimum spanning tree in kruskal's algorithm don't create a circle.

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  

The code above should be correct and is posted for the sake of completness. Following up we have kruskal's algorithm implementation:

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 stackoverflow)
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

The part where I have if bfs(V,startnode) == bfs(V, ): is where I'm kinda stuck, how can I complete this if condition. I tried extending bfs to include some form of "circle detection". That did not work however.

Answer 1

I can't help with your code, but I can explain the mathematical principles.

By the way, the problem of circle detection is exactly why Prim's algorithm is better to use than Kruskal's.

If you really want to detect a circle, then you need to think about the edge that you are just about to add. Will it create a cycle? If not, then you are fine.

If you are about to add an edge between node A and node B, then first search if there is an existing path between A and B. If such a path exists, then you must not add the edge AB. If such a path does not exist then you are safe to add the node.