Алгоритм Крускала: проверить, создает ли новое ребро окружность - PullRequest
Новая
       51

Алгоритм Крускала: проверить, создает ли новое ребро окружность

1 голос
/ 04 июня 2019

Я пытаюсь реализовать алгоритм Крускала в Python 3.7.

Поэтому я написал программу "bfs" для поиска в ширину, которую я хочу использовать, чтобы проверить, что ребра, добавляемые в минимальное остовное дерево в алгоритме Крускала, не создают круг. 

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

Код выше должен быть верным и опубликован для полноты картины. В продолжение мы имеем реализацию алгоритма Крускала: 

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

Часть, где у меня есть if bfs(V,startnode) == bfs(V, ):, где я как бы застрял, как я могу выполнить это, если условие. Я попытался расширить bfs, чтобы включить некоторую форму "обнаружения круга". Однако это не сработало.

1 Ответ

1 голос
/ 04 июня 2019

Вместо добавления ребра и проверки круга, сравните деревья, прежде чем добавлять ребро, и добавляйте его, только если вершины не связаны.Кроме того, работа с UNION-FIND будет более эффективной.

...