DFS 搜索不返回我列表中的某些节点

Question

我正在使用 DFS 的这个实现来获取我在函数中指定的根的节点，但是对于 adjLists1，当我调用 2 作为根时，我使用了一个错误。 . 1 和 3 return 它们的子节点，但 2 不是。不确定我在这里做错了什么。我得到的错误是：

Traceback (most recent call last):
2  5    File "DFS2.py", line 42, in <module>
    dfs_iterative(adjLists1, 2)
  File "DFS2.py", line 17, in dfs_iterative
    if(not visited[w]):
IndexError: list index out of range

节目：

def dfs_iterative(adjLists, s):
    stack = []
    stack.append(s)
    n = len(adjLists)
    visited = []
    for i in range(0,n):
        visited.append(False)

    while(len(stack)>0):
        v = stack.pop()
        if(not visited[v]):
            visited[v] = True
            print(v, " ", end='')

            stack_aux = []
            for w in adjLists[v]:
                if(not visited[w]):
                    stack_aux.append(w)
            while(len(stack_aux)>0):
                stack.append(stack_aux.pop())


# ------------------------------------------------------------------

#                0      1     2      3    4        5         6        7   8
adjLists1 = [ [1,2,3], [4], [5,6], [7,8], [], [9,10,11], [12,13,14], [], [] ]

dfs_iterative(adjLists1, 2)

Answer 1

您可以解决没有空白子节点的问题，方法是使用列表中的最大值并适当防止索引：

你的代码还可以再简化一点：

import itertools as it

def dfs_iterative(adjLists, s):
    stack = [s]
    n = len(adjLists)
    visited = [False] * (max(it.chain(*adjLists))+1)

    while stack:
        v = stack.pop()
        if visited[v]:
            continue

        visited[v] = True
        print(v, " ", end='')
        if v >= n:   # Guard against trying to index with v
            continue
        for w in adjLists[v]:
            stack.append(w)

>>> adjLists1 = [ [1,2,3], [4], [5,6], [7,8], [], [9,10,11], [12,13,14], [], []]
>>> dfs_iterative(adjLists1, 2)
2  6  14  13  12  5  11  10  9

注意：您永远不会索引 0，因此永远不会探索 [1, 2, 3]。

DFS 搜索不返回我列表中的某些节点

DFS search not returning certain nodes in my list

python

search

depth-first-search