CODEWITHSUNDEEP
pythongraphdepth-first-search
Liondancer
Liondancer

Reputation: 16469

Depth first search has wrong output when cycle is encountered

I am trying to implement a depth first search but I am having trouble when it comes to cycles within the directed graph.

directed_graph = {
    'a': ['b'],
    'b': ['c', 'd', 'e'],
    'c': ['d', 'e'],
    'd': ['a', 'e'],
    'e': ['f'],
    'f': [],
    'g': ['d']
}

Ignore the weights of each edge:

enter image description here

There is a cycle from B -> C -> D -> A -> B

def dfs(graph, start, end, visited=[]):
    if start == end:
        return True
    if start is None or end is None:
        return False
    queue = [start]
    if start not in visited:
        visited = visited + [start]

    node = queue.pop(0)

    for i in graph[node]:
        if i == end:
            return True
        if i not in visited:
            visited.append(i)
            return dfs(graph, i, end, visited)
    return False

When I run the function with start = 'b' and end = 'f' I get an output of False when if should be True

Upvotes: 2

Views: 182

Answers (1)

f9c69e9781fa194211448473495534
f9c69e9781fa194211448473495534

Reputation: 4620

The problem with your program is that it only considers the first non-visited neighbor of each vertex. In the for loop, for each non-visited neighbor, dfs is called recursively. However, the result of this call will then be returned (meaning the for loop is aborted). Therefore, other non-visited neighbors will not be considered.

In your example graph, the program visits the starting vertex a first. It then considers the first non-visited neighbor, which is b. At b it goes to the first non-visited neighbor, which is d. At d, the first non-visited neighbor is a. Since a has no non-visited neighbors (the only neighbor is b, which has already been visited), the for loop completes for a and the return False is reached for the dfs call for a. Back in the dfs call for d, the for loop will then be aborted to return the False given by the dfs call for a. This way, the False will be propagated up the call chain, resulting in the final False returned by your initial query.

To fix this, change the recursive call to dfs, such that the for loop is only aborted when the call returned True:

            if dfs(graph, i, end, visited):
              return True

With this fix, your program will give True for start = 'b' and end = 'f'.

Upvotes: 1

Related Questions