我正在研究有向图的 DFS，如何到达没有任何边指向的节点？

Question

http://homepage.cs.uiowa.edu/~hzhang/c31/ch09-probs.pdf

问题是上面PDF中的9.2。我很困惑如何到达节点 E，因为它只有远离节点的边； None 指向节点 E。 感谢您的帮助。

Answer 1

如果要DFS遍历所有节点，必须对每个节点进行迭代，检查该节点是否被访问，并使用该节点开始DFS。

    procedure DFS(G,v):
      label v as discovered
      for all edges from v to w in G.adjacentEdges(v) do
          if vertex w is not labeled as discovered then
              recursively call DFS(G,w)

    procedure traverse_by_DFS(G):
        for v in G:
            if v is dicovered:
                continue
            DFS(G, v)

Answer 2

这是一个有技巧的问题。你没有命中节点 E，因为你被迫从节点 A 开始。这是给定一个不是真正根的起始节点的效果 - 结果是不完整的遍历。