我的 DFS 无法处理简单的图形 [Python]

Question

下面是我的 DFS[深度优先搜索] 代码，我的代码可以处理复杂的图形，但无法像我给出的那样处理简单的图形，所以我的问题那是怎么解决的？我正在递归。任何形式的帮助表示赞赏。

graph = { 'A' : ['B','S']}

def dfs(graph,start_node,visited):
    if start_node:
        if start_node not in visited:
            visited.append(start_node)
            for node in graph[start_node]:
                  dfs(graph,node,visited)
    else:
        return visited
    return visited

visited=dfs(graph,"A",[])
print(visited)

Answer 1

您如何表示图表？如果它是作为标准图（具有 2 向边）表示为由节点键入的字典，其中值是相邻节点的列表，那么您的 "graph" 根本不是图，因为它缺少边列表对于 'B' 和 'S'。但是，为什么要将它用作测试用例？此类输入的唯一相关问题是，您是否想测试您的代码是否在它们上优雅地失败（您的代码没有——但正确的错误处理与您的问题无关）。

另一方面，如果这些是有向图，那么您的示例就有意义（将值解释为对应于 outgoing 边，键是具有外向边的节点） .但在那种情况下，您无法处理终端节点。您可以在递归之前显式检查节点是否在字典中，或者将终端节点的直接可达节点列表视为隐式 [] 并使用字典 get() 方法 return 在那些情况下：

def dfs(graph,start_node,visited):
    if start_node:
        if start_node not in visited:
            visited.append(start_node)
            for node in graph.get(start_node,[]):
                  dfs(graph,node,visited)
    else:
        return visited
    return visited

这将按预期工作，打印 ['A', 'B', 'S']。

我的 DFS 无法处理简单的图形 [Python]

My DFS can't handle simple graph [Python]

python

recursion

microsoft-distributed-file-system