Алгоритм подсчета связных компонентов графа в Python

Я пытаюсь написать скрипт, который подсчитывает связанные компоненты графа, и не могу найти правильное решение. У меня есть простой граф с 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)

Может ли кто-нибудь помочь мне найти ошибку?


python graph algorithm graph-theory depth-first-search
person Tomas Novotny    schedule 23.10.2010    source источник
comment
В get_connected_components_number(graph) может показаться, что вы помечаете все узлы как посещенные, а затем подсчитываете количество узлов без соединений (очевидно, 2). Честно говоря, я не знаю, что вы пытаетесь сделать с помощью этой программы.   -  person dln385    schedule 23.10.2010

Ответы (2)


arrow_upward
4
arrow_downward

Иногда проще написать код, чем прочитать его.

Проведите несколько тестов, я почти уверен, что это всегда будет работать, если каждое соединение является двунаправленным (например, в вашем примере).

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

Обратите внимание, что я удалил идентификатор из информации об узле, поскольку его позиция в массиве является его идентификатором. Дайте мне знать, если эта программа не делает то, что вам нужно.

person dln385    schedule 23.10.2010
comment
Большое спасибо, ваш код отлично работает для данного ввода, но, вероятно, он не совсем правильный. Например, для входных узлов = [[[2,3], False], [[1,3], False], [[1,2], False], [[5,6], False], [[ 4,6], False], [[4,5], False], [[8], False], [[7,9], False], [[8], False], [[], False] , [[], False], [[], False]] должен вернуть 6. (График с 6 компонентами связности — 1-2-3-1, 4-5-6-4, 7-8-9, 10 , 11 , 12) - person Tomas Novotny; 24.10.2010
comment
Я изменил идентификатор точки на ее позицию в массиве. Таким образом, первая точка имеет идентификатор 0, вторая точка — идентификатор 1 и т. д. Вот входные узлы, которые вы дали с каждым идентификатором, уменьшенным на 1, что дает правильный ответ 6: [[[1,2], False], [ [0,2], Ложь], [[0,1], Ложь], [[4,5], Ложь], [[3,5], Ложь], [[3,4], Ложь],[ [7], Ложь], [[6,8], Ложь], [[7], Ложь], [[], Ложь], [[], Ложь], [[], Ложь]] - person dln385; 24.10.2010

arrow_upward
6
arrow_downward

Структура данных с непересекающимся набором действительно поможет вам написать здесь понятный код, см. Википедию.

Основная идея заключается в том, что вы связываете набор с каждым узлом в вашем графе и для каждого ребра вы объединяете наборы двух его конечных точек. Два множества 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)
person Community    schedule 24.10.2010
comment
Это решение работает, даже если соединения не являются двунаправленными и узлы не образуют иерархическую древовидную структуру. Очень впечатляюще. - person dln385; 26.10.2010