1
これは、DFSツリーのプリオーダートラバーサルに対応するDFSプリオーダー頂点番号付けであり、第2は、DFSツリーのポストオーダートラバーサルに対応するポストオーダー番号付けです。グラフプリオーダー/ポストオーダートラバーサル?
誰かがこの注文をどのように受け取ったのか説明できますか?私はバイナリツリーにのみプレオーダーまたはポストオーダーを適用する方法しか知っていないためです。
Initialize clock to 1
PreVisit(v):
pre[v] <- clock
clock <- clock + 1
PostVisit(v):
post[v] <- clock
clock <- clock + 1
Explore(v):
visited[v] = true
PreVisit(v)
for all u adj to v:
if u is not visited:
Explore(u)
PostVisit(v)
注:それは非常に簡単で、単なるDFSだ、あなたの例でステップすることで、この擬似コードのステップに従うことを試してみて、あなたは、アルゴリズムを理解する
DFSの仕組みをご存じですか? Preorder 1.ルートノードを最小重みで1つ選択してから2.searchを実行し、次に2.searchを実行し、親ノード以外の他のすべてのノードを選択してサイクルを形成しないで、ステップ2を繰り返してすべてをカバーするまで繰り返す頂点 – CY5
DFSは、(バイナリ)ツリーと同様に、どのグラフでも同様に機能します。主な違いは、循環グラフ(木には発生しません)のサイクルをアルゴリズムが明示的に防止しなければならない点です。これは、ノード値がいくつかの定義された規則に従うかどうかを暗黙のうちに考慮することができます。 – user2864740