Алгоритм подсчета связных компонент графа на Python
-
25-09-2019 - |
Вопрос
Я пытаюсь написать скрипт, который подсчитывает связные компоненты графа, но не могу найти правильное решение.У меня есть простой граф с 6 узлами (вершинами), узлы 1 и 2 соединены, а узлы 3 и 4 соединены (6 вершин;1-2,3-4,5,6).Итак, граф содержит 4 компонента связности.Я использую следующий скрипт для подсчета подключенных компонентов, но получаю неверный результат (2).
nodes = [[1, [2], False], [2, [1], False], [3, [4], False], [4, [3], False], [5, [], False], [6, [], False]]
# 6 nodes, every node has an id, list of connected nodes and boolean whether the node has already been visited
componentsCount = 0
def mark_nodes( list_of_nodes):
global componentsCount
componentsCount = 0
for node in list_of_nodes:
node[2] = False
mark_node_auxiliary( node)
def mark_node_auxiliary( node):
global componentsCount
if not node[2] == True:
node[2] = True
for neighbor in node[1]:
nodes[neighbor - 1][2] = True
mark_node_auxiliary( nodes[neighbor - 1])
else:
unmarkedNodes = []
for neighbor in node[1]:
if not nodes[neighbor - 1][2] == True: # This condition is never met. WHY???
unmarkedNodes.append( neighbor)
componentsCount += 1
for unmarkedNode in unmarkedNodes:
mark_node_auxiliary( nodes[unmarkedNode - 1])
def get_connected_components_number( graph):
result = componentsCount
mark_nodes( graph)
for node in nodes:
if len( node[1]) == 0: # For every vertex without neighbor...
result += 1 # ... increment number of connected components by 1.
return result
print get_connected_components_number( nodes)
Может ли кто-нибудь помочь мне найти ошибку?
Решение
Иногда проще написать код, чем прочитать его.
Проведите несколько тестов, я почти уверен, что это всегда будет работать, пока каждое соединение является двунаправленным (как в вашем примере).
def recursivelyMark(nodeID, nodes):
(connections, visited) = nodes[nodeID]
if visited:
return
nodes[nodeID][1] = True
for connectedNodeID in connections:
recursivelyMark(connectedNodeID, nodes)
def main():
nodes = [[[1], False], [[0], False], [[3], False], [[2], False], [[], False], [[], False]]
componentsCount = 0
for (nodeID, (connections, visited)) in enumerate(nodes):
if visited == False:
componentsCount += 1
recursivelyMark(nodeID, nodes)
print(componentsCount)
if __name__ == '__main__':
main()
Обратите внимание, что я удалил идентификатор из информации об узле, поскольку его позиция в массиве является его идентификатором.Дайте мне знать, если эта программа не делает то, что вам нужно.
Другие советы
Disastrapted Datastructure действительно поможет вам написать четкий код здесь, см. Википедия.
Основная идея заключается в том, что вы связываете набор с каждым узлом в вашем графике, и для каждого края вы объединяете наборы двух конечных точек. Два набора x
а также y
одинаковы, если x.find() == y.find()
Вот самая наивная реализация (которая имеет плохой сложность наихудшего случая), но есть пара оптимизации класса Disjointset на странице Википедии, выше которой в нескольких дополнительных линиях кода делают этот эффективный. Я пропустил их для ясности.
nodes = [[1, [2]], [2, [1]], [3, [4]], [4, [3]], [5, []], [6, []]]
def count_components(nodes):
sets = {}
for node in nodes:
sets[node[0]] = DisjointSet()
for node in nodes:
for vtx in node[1]:
sets[node[0]].union(sets[vtx])
return len(set(x.find() for x in sets.itervalues()))
class DisjointSet(object):
def __init__(self):
self.parent = None
def find(self):
if self.parent is None: return self
return self.parent.find()
def union(self, other):
them = other.find()
us = self.find()
if them != us:
us.parent = them
print count_components(nodes)