Depth First Search Output Changes on Every Run

Question

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

Answer 1

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