1 
procedure explore(G,v)
Input: G=(V,E) is a graph; v ∈ V
Output: visited(u) is set to true for all nodes u reachable from v

visited(v) = true;
previsit(v)
for each edge (v,u) ∈  E:
    if not visited(u): explore(u)
postvisit(v)

重写探索过程（上图），使其非递归（即显式使用堆栈）。应该定位对 previsit 和 postvisit 的调用，以便它们具有与递归过程中相同的效果。

解决方案：

procedure explore(G; u)
S = (empty stack)
push(S, u)
while S is not empty:
  v = top(S)
  if not visited[v]:
    visited[v] = true
    previsit(v)
  if there is an edge (v; w) ∈ E with visited[w] = false:
    push(S, w)
  else: (we're done with v, the node at the top of the stack)
    pop(S)
    postvisit(v)

有人可以帮我理解这个伪代码吗，我不确定 Stack 在这种情况下是如何工作的。有人可以带我看一下这段代码，以便我了解它是如何工作的

4

0 回答 0