algorithm - 如何证明 BFS 有向图遍历算法是可终止的？

Question

如何证明 BFS 有向图遍历算法是可终止的？（我从这里复制伪代码）输入：图 G 和 G 的根 v

  procedure BFS(G,v):
      create a queue Q
      enqueue v onto Q
      mark v
      while Q is not empty:
          t ← Q.dequeue()
          if t is what we are looking for:
              return t
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

Answer 1

每个节点最多被访问（标记）一次，因此在最坏的情况下，您将标记所有节点，然后算法将终止。