Python: Подсчет количества подключенных компонентов в прил. представление графика в виде списка - PullRequest
Новая
       44

Python: Подсчет количества подключенных компонентов в прил. представление графика в виде списка

0 голосов
/ 17 июня 2020

Я пытаюсь написать программу на python, которая подсчитывает количество циклов (связанных компонентов) в графе, представленном с использованием списка смежности (dict () в python).

Обычно я запускаю DFS и проверяю, посещена ли уже соседняя вершина и не является ли эта вершина родительской для текущей вершины. Если это так, то на графике существует цикл. Затем я подсчитываю, сколько раз возникает такая ситуация. 

def count_cycles(graph, start, visited, count=0): 
    visited[start] = True
    for next in graph[start]:
        if not visited[next]:
            count_cycles(graph, next, visited, count)
        elif start != next:
            count += 1
    return count

if __name__ == "__main__":
    graph = {
        3: {10},
        4: {8},
        6: {3},
        7: {4, 6},
        8: {7},
        10: {6}
    }
    visited = [False] * (max(graph)+1)
    print(count_cycles(graph, 8, visited))

В этом примере на выходе должно быть 2, но он печатает 1. Я подозреваю, что есть проблема с моей DFS, но я не могу чтобы выяснить это точно.

Есть предложения?

1 Ответ

1 голос
/ 17 июня 2020

Понятно, вам нужно обновить счетчик через рекурсивный вызов. 

def count_cycles(graph, start, visited): 
    visited[start] = True
    count = 0
    for next in graph[start]:
        if not visited[next]:
            count += count_cycles(graph, next, visited)
        elif start != next:
            count += 1
    return count

if __name__ == "__main__":
    graph = {
        3: {10},
        4: {8},
        6: {3},
        7: {4, 6},
        8: {7},
        10: {6}
    }
    visited = [False] * (max(graph)+1)
    print(count_cycles(graph, 8, visited))
...