私は有向グラフのDFSに取り組んでいます、どのようにエッジを指さずにノードに到達するのですか？

Question

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

問題は上記のPDFの9.2です。私はそれがノードから離れて指された辺しか持たないので、ノードEにどのように到達するのか混乱しています。ノード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

これはおもしろい質問です。あなたはノードAから始める必要があるので、ノードEを押すことはありません。これは真のルートではない開始ノードが与えられた場合の効果です。結果として、完全なトラバーサルが得られます。