http://i.stack.imgur.com/sEJKz.png
画像はグラフです。これは正しい深さ優先トラバーサルですか? それとも、私はその考えを完全に間違っていますか？dfs についての私の理解は出発点として与えられ、隣接するすべてのノードを調べます。次に、任意に 1 つを選択し、そのノードを再帰的に「訪問」します。v から始めて、ノード 2 を選択して次に進みます。1 から 8 までの数字はパスを示します。
編集: 数字の 2 と 3 を混同しているようです! それらを交換する必要があります。
あなたが示しているのは、考えられる正しい DFS 検索順序です。あなたが言ったように、DFSは再帰的に訪問し、すでに訪問したノードをマークします。未訪問のノードに再帰できないポイントに到達すると、そのようなポイントが存在するか、すべてのノードが訪問済みとしてマークされるため、検索が終了するまでバックトラックします。
あなたの場合、1、2、および 3 にアクセスします。3 で、2 に戻り、次に 4、5、6、7、8 に進みます。その後、バックトラックしますが、すべてのノードがアクセスされるため、検索はこれで終了します。訪問順。
この場合、3 とマークされたノードは、2 または 8 である可能性もあります。たとえば、DFS は (図のラベルを使用して) 1、2、4、5、6、7、8、2 に戻る可能性があります。 3、終了します。
