Python. DFS graph traversal, correct output?

Question

I'm currently getting to grips with graph traversal in Python.

Given the following graph:

Implemented using this dictionary:


graph = {'0': set(['1', '2', '3']),
         '1': set(['0','2']),
         '2': set(['0','1','4']),
         '3': set(['0']),
         '4': set(['2'])}

Am I correct in thinking a depth first search traversal beginning from node 0 should return [0,1,2,4,3]?

My dfs function returns [0,3,1,2,4] and so I am wondering if I have something wrong in my implementation:

def dfs(graph, node,visited=None):
    if visited is None:
        visited=set()
        
    if node not in visited:
        print (node,end=' ')
        visited.add(node)
        
        for neighbour in graph[node]:
            dfs(graph,neighbour,visited=visited)

dfs(graph,'0')

Help and advice appreciated.

chrslg · Accepted Answer · 2023-01-14 14:54:27Z

1

No you aren't.

You would be right to say that traversal order COULD be [0,1,2,4,3]. Not that it should. The only thing you know about traversal order is that you explore, among everything explorable, first the descendant of the last explored node. But among those, nothing tells you any order.

And the implementation you've chosen make that extra clear, since set in python don't have a specific order (but even if you'd chosen list instead of set, and written an implementation that, among the child of the most recently explored nodes, explores the first child of the list, leading indeed to [0,1,2,4,3], that would be just your implementation, not a rule about DFS. Nothing says that you should favor one child against another; or, to be more accurate, since you have to choose one, nothing says in which order. That is totally implementation dependent).

So from your graph, starting from 0, a DFS traversal order could be any of

0,1,2,4,3
0,2,1,4,3
0,2,4,1,3
0,3,1,2,4
0,3,2,1,4
0,3,2,4,1

(Plus those I may have forgotten)

answered Jan 14, 2023 at 14:54

chrslg

15.2k11 gold badges26 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

r0bt Over a year ago

Thanks for your response. I realised that my use of set in the graph instantiation is what led to unexpected results but your explanation clarifies why. Thank you!

r0bt · Accepted Answer · 2023-01-14 14:48:41Z

0

Never mind.

I realise my error was due to how I had initiated the graph. I mistakenly passed in sets. Using the following seems to produce the expected results:

graph = {'0': ['1', '2', '3'],
         '1': ['0','2'],
         '2': ['0','1','4'],
         '3': ['0'],
         '4': ['2']}

dfs(graph, '0')

answered Jan 14, 2023 at 14:48

r0bt

6096 silver badges21 bronze badges

1 Comment

chrslg Over a year ago

No, that is not the accurate answer. You made no mistake using set. In fact it is even the more faithful implementation: DFS doesn't specify a priority order among childs, and neither does set. So, even the uncertainty is conserved. It is because you've used set indeed, that you don't end up with order 0,1,2,4,3. But conclusion should not be "so, I shouldn't have used sets", but "so, I shouldn't expect order to be exactly 0,1,2,4,3". 0,1,2,4,3 is not the only possible traversal order for DFS. Remember, DFS and BFS are ambiguous. They specify only partially the traversal order.

Collectives™ on Stack Overflow

Python. DFS graph traversal, correct output?

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related