Depth First Search Output Changes on Every Run

user_13055097 0
Viewed 40

I have the below code for depth first search:

def dfs(graph, vertex):
    visited = set()
    stack = [vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex])
    return visited

def main():
    test_graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    print(dfs(test_graph, 'A'))

if __name__ == '__main__':
    main()

On every execution I'm getting a different output.

Is there any change I can make such that the output always starts with the value of vertex (in this case A)?

depth-first-search graph python
2 Answers

in Python, a set isn't ordered. you can use collections.OrderedDict to keep the keys in order of insertion, while also having not in work in O(1) like in a set:

from collections import OrderedDict

def dfs(graph, vertex):
    visited = OrderedDict()
    stack = [vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited[vertex] = True
            stack.extend(graph[vertex])
    return list(visited.keys())

def main():
    test_graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    print(dfs(test_graph, 'A'))

if __name__ == '__main__':
    main()
user_50523650

Your algorithm is fine, and it does the same thing on every run. The catch is with the use of set for returning the output. A set isn't ordered, and you may get different results on different runs. You can solve that in various ways - one would be to create a list out of the set and sort it before you return from the dfs function.

Another solution would be to use a list in the first place: 

def dfs(graph, vertex):
    visited = []
    stack = [vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            stack.extend(graph[vertex])

    return visited
user_11055600
Related