如何证明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
每个节点最多被访问(标记)一次,所以在最坏的情况下,你将标记所有节点,然后算法将终止。