如何跟踪和显示处于同一级别的已访问节点？

Question

我对图上的bfs算法有疑问。如下图所示，我希望找到从“C”到“L”的路径，并以正确的顺序获得所有展开的节点。我从下面显示的代码中得到了正确的结果，但我找不到跟踪/显示已访问节点（即节点（D）和（H））的方法

到目前为止，我脑海中的解决方案是首先获取处于同一级别的所有节点，然后在将其放入队列之前进行排序

注:

1. 平局断路器按字母顺序排列：我可以使用itemgettere实现
2. 你可以找到blhsinghere发布的原始代码

import collections
from operator import itemgettere

class graph:


    def __init__(self, path=None):
        self.graph = {'A': ['B', 'C', 'D', 'E'], 'B': ['A', 'F'], 'F': ['B', 'J'], 'J': ['F', 'K'], 'C': ['A', 'G'],
                      'G': ['C', 'H', 'K'], 'K': ['G', 'J'], 'D': ['A', 'H'], 'H': ['D', 'G', 'L'], 'L': ['H'],
                      'E': ['A', 'I'], 'I': ['E', 'M'], 'M': ['I']}

    def bfs(self, graph, root, goal):
        seen, queue = {root}, collections.deque([(root, 0)])
        visit_order = []
        levels = []

        while queue:

            vertex, level = queue.popleft()

            # Stop when the goal is reached
            if goal in visit_order:
                break

            visit_order.append(vertex)
            levels.append(level)

            for node in graph.get(vertex):
                if node not in seen:
                    seen.add(node)
                    queue.append((node, level + 1))

            # sort queue by level, then alphabetically
            temp_queue = list(queue)
            temp_queue.sort(key=itemgetter(1, 0))
            queue = collections.deque(temp_queue)

        print(visit_order)
        print(levels)


g = graph()
g.bfs(g.graph, 'C', 'L')

#output = ['C', 'A', 'G', 'B', 'D', 'E', 'H', 'K', 'F', 'I', 'J', 'L']
#[0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3]

Answer 1

只是澄清一下，图没有方向，所以当你在节点“A”时，它的邻居实际上是{B，C，D，E}，而不仅仅是{B，D，E}，除非你明确排除了前一个节点“C”

我认为这个问题最棘手的部分是，你想知道一个节点以前是否被访问过，但也要排除当前节点的上一个节点，它肯定被访问过

我修改了示例代码，如下所示。 我逐层遍历图表，因此不需要显式跟踪级别信息，但我将其保留在那里，以防有帮助

class graph:
    def __init__(self, path=None):
        self.graph = {'A': ['B', 'C', 'D', 'E'], 'B': ['A', 'F'], 'F': ['B', 'J'], 'J': ['F', 'K'], 'C': ['A', 'G'],
                      'G': ['C', 'H', 'K'], 'K': ['G', 'J'], 'D': ['A', 'H'], 'H': ['D', 'G', 'L'], 'L': ['H'],
                      'E': ['A', 'I'], 'I': ['E', 'M'], 'M': ['I']}

    def bfs(self, graph, root, goal):
        seen, currentLevel = set(), [(None, None, root)]
        visit_order = []
        level = 0 # you can use the level info if needed
        while currentLevel:
            nextLevel = []
            for v0, v1, v2 in currentLevel:
                if v2 not in seen:
                    visit_order.append(v2)
                    seen.add(v2)
                    for v3 in graph[v2]:
                        nextLevel.append((v1, v2, v3))
                elif v2 != v0:
                    visit_order.append(f"({v2})")
            level += 1

            # Stop when the goal is reached
            if goal in seen:
                break

            # all nodes in nextLevel are at the same level already. Just sort alphabetically
            currentLevel = sorted(nextLevel, key=lambda p: p[2])

        print(visit_order)

g = graph()
g.bfs(g.graph, 'C', 'L')
# output = ['C', 'A', 'G', 'B', 'D', 'E', 'H', 'K', '(D)', 'F', '(H)', 'I', 'J', 'L']