Why don’t my Depth-First-Search code working properly?

it’s my 1st question so go easy on my thing ! as far as i know Depth-First Search has to search “Depth” first

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
         [], 
         [2,3,8], 
         [1,7],   
         [1,4,5], 
         [3,5],
         [3,4],
         [7],
         [2,6,8],
         [1,7]]

visited = [False] * 9
print(dfs(graph,1,visited))

these are the DFS code and a example

If we do “print(dfs(graph,1,visited))”, we can get the result “1 2 7 6 8 3 4 5”.

this is natural. My question is that if we change the node? graph info? (look at changed below graph info)

graph = [
     [], 
     [2,3,6],
     [1,7],   
     [1,4,5], 
     [3,5],
     [3,4],
     [1,7], (*)
     [2,6,8],
     [7] (*)
]

Then, do print(dfs(graph,1,visited)) again. we can get the result “1 2 7 6 8 3 4 5”.

It’s not Depth-First-Search, right? It’s because “1 2 7 8 6 3 4 5” (6<->8) is answer

I think something is missing in code or I miss a premise

Please Let me know…

+)My English is not good. If you understand my question, I’d appreciate it if you could revise the sentence or words

+)I’m sorry I can’t upload image for graph

Answer

Both the output from the code as your own idea represent valid depth-first traversals. The traversal can choose which child to visit first. So whether 6 or 8 is visited first, when looking at the children of 7, depends on the order its children are iterated. Since the data structure stores them in numerical order, it is expected that 6 is visited first.

Here is the graph, with the relevant path in color:

Advertisement

Answer