为什么我的深度优先搜索代码不能正常工作？

Question

这是我的第一个问题，请放轻松！据我所知，深度优先搜索必须首先搜索“深度”

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

这些是 DFS 代码和示例

如果我们执行“print(dfs(graph,1,visited))”，我们可以得到结果“1 2 7 6 8 3 4 5”。

这很自然。我的问题是，如果我们改变节点？图信息？（查看下方图表信息的变化）

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

然后，再次打印(dfs(graph,1,visited))。我们可以得到结果“1 2 7 6 8 3 4 5”。

这不是深度优先搜索，对吧？这是因为 "1 2 7 8 6 3 4 5" (6<->8) 是答案

我认为代码中缺少某些东西或者我错过了一个前提

请告诉我...

+)我的英语不好。如果您理解我的问题，请修改句子或单词，我将不胜感激

+)抱歉我无法上传图表的图片

Answer 1

代码的输出和您自己的想法都代表有效的 depth-first 遍历。遍历可以选择先访问哪个child。所以先访问 6 还是先访问 8，在查看 7 的 children 时，取决于它的 children 被迭代的顺序。由于数据结构按数字顺序存储它们，因此预计首先访问 6。

这是图表，相关路径用颜色表示：

为什么我的深度优先搜索代码不能正常工作？

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

python

depth-first-search