CODEWITHSUNDEEP
pythongraph-theorydepth-first-searchconnected-components
swing1234
swing1234

Reputation: 233

Python: Counting number of connected components in adj. list representation of graph

I am trying to write a program in python that counts the number of cycles (connected components) in a graph represented using an adjacency list (dict() in python).

Basically, I run DFS and check if an adjacent vertex is already visited and that vertex is not a parent of current vertex. If that's the case, then there exists a cycle in the graph. Then I count the number of times that situation occurs.

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

In the example, the output should be 2, but it prints 1. I suspect there is an issue with my DFS, but I am not able to figure it out exactly.

Any suggestions?

Upvotes: 0

Views: 804

Answers (1)

JimmyCarlos
JimmyCarlos

Reputation: 1952

Got it, you needed to update count through your recursive call.

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

Upvotes: 2

Related Questions