algorithm - 术语 "VISITED"的 BFS 和正确性

Question

mark x as visited
list L = x
tree T = x
while L nonempty
    choose some vertex v from front of list
    process v
    for each unmarked neighbor w
        mark w as visited
        add it to end of list
        add edge vw to T

大多数代码会选择在访问相邻节点之前将其标记为已访问。先添加所有邻居然后再访问它们在技术上不是正确的吗？

list L = x
tree T = x
while L nonempty
    choose some vertex v from front of list
    if (V NOT YET VISITD)
        MARK V AS VISITED HERE
        for each unmarked neighbor w
            add it to end of list
            add edge vw to T

为什么每个 BFS 似乎都将节点标记为已访问，而您甚至还没有访问它们？我正在尝试为 BFS 找到理论上正确的代码。哪一个是正确的？

Answer 1

两种算法都有效，但第二个版本可能会将同一节点添加到列表 L 两次。这不会影响正确性，因为会额外检查是否访问了节点，但会增加内存消耗并需要额外检查。这就是为什么您通常会在教科书中看到第一个算法。