使用字典进行深度优先搜索？

Question

我正在尝试使用字典进行深度优先搜索，其中键是将要访问的下一个节点，值是前一个节点，但有些地方不太对。到目前为止我有：

from collections import deque
class Graph:

    def __init__(self, n):
        self.adj = {}
        for i in range(n):
            self.adj[i] = []

    def are_connected(self, node1, node2):
        return node2 in self.adj[node1]

    def adjacent_nodes(self, node):
        return self.adj[node]

    def add_node(self):
        self.adj[len(self.adj)] = []

    def add_edge(self, node1, node2):
        if node1 not in self.adj[node2]:
            self.adj[node1].append(node2)
            self.adj[node2].append(node1)

    def number_of_nodes():
        return len()

def DFS(G, node1):
    S = [node1]
    marked = {}
    pred = {}
    for node in G.adj:
        marked[node] = False
    while len(S) != 0:
        current_node = S.pop()
        if not marked[current_node]:
            marked[current_node] = True
            for node in G.adj[current_node]:
                # if node == node2:
                #     return True
                S.append(node)
        if not marked[node]:
            pred[node] = current_node
    pred[current_node] = node
    return pred

当我打电话时：

G = Graph(20)
G.add_edge(1, 2)
G.add_edge(2, 3)
G.add_edge(3, 4)
G.add_edge(0, 1)
G.add_edge(4, 5)
G.add_edge(5, 6)
G.add_edge(6, 7)
G.add_edge(4, 6)
G.add_edge(2, 6)
G.add_edge(8, 9)
G.add_edge(10, 3)
G.add_edge(2, 3)

print(DFS(G, 1))

我得到 {0: 1, 6: 2, 10: 3, 1: 6} 但这不可能是正确的，因为 G 中有许多节点甚至没有被访问过，我不太明白问题是什么。感谢您的帮助！

Answer 1

您将 if not marked[node] 条件放在了错误的位置。

def DFS(G, node1):
    S = [node1]
    marked = {}
    pred = {}
    for node in G.adj:
        marked[node] = False
    while len(S) != 0:
        current_node = S.pop()
        if not marked[current_node]:
            marked[current_node] = True
            for node in G.adj[current_node]:
                # if node == node2:
                #     return True
                S.append(node)
                if not marked[node]:
                    pred[node] = current_node
    pred[current_node] = node
    return pred

输出将是：{2: 1, 0: 1, 3: 4, 6: 2, 5: 4, 7: 6, 4: 6, 10: 3, 1: 6}

这是你期待的吗？

Answer 2

1: 你想要return DFS 函数中的字典无法显示。假设我们有两条路径到节点 1，分别是节点 0 和节点 2，如果我们得到 {1:2}，那么 {1:0} 将替换 {1:2}，您可能会丢失一些节点路径。

2：做深度优先搜索，需要“走到尽头”。函数中的数组 S 进行循环，但首先进行广度。

我用递归函数修改你的代码：

def DFS(G, node1, marked = []):
    S = [node1]
    pred = []
    while len(S) != 0:
        current_node = S.pop()
        if current_node not in marked:
            marked.append(current_node)
            pred.append(current_node)
            for node in G.adj[current_node]:
                # if node == node2:
                #     return True
                pred.extend(DFS(G, node, marked))
    return pred

我运行你的测试用例。这是打印结果： [1, 2, 3, 4, 5, 6, 7, 10, 0]

希望回答对你有帮助嗯

使用字典进行深度优先搜索？

Depth first search using a dictionary?

python

algorithm

depth-first-search