0

グラフについて読む..すべてのグラフは、その強く接続されたコンポーネントのDAG有向非循環グラフであると言われています。したがって、これらの強く接続されたコンポーネントを見つけるには、グラフのシンク部分でノードを見つける必要があります..ここでさらに説明するには、投稿番号と前番号を説明する必要があります..

pre no :- preordering は、深さ優先探索アルゴリズムによって最初にアクセスされた順序での頂点のリストです。したがって、対応する前番号。

同様に post no :- postordering は、アルゴリズム DFS によって最後にアクセスされた順序の頂点のリストです。その対応するポスト番号

現在、最高の投稿はソースノードを提供します（真の理解）が、投稿の昇順がシンク部分を提供しないのはなぜですか？

私の疑問は次のとおりです:-グラフを逆にしてシンクを見つけ、それによって接続されたコンポーネントを見つける必要があるのはなぜですか。同じグラフで、ポスト番号が増加する順序でアルゴを実行しないのはなぜですか (最も低いポスト番号がシンク接続コンポーネントに存在するため)。

なぜグラフを反転する必要があるのですか?

4

2 に答える 2

1

それは、強連結成分の特性によるものです。コンポーネントのすべてのノードがコンポーネントの他のすべてのノードに到達する必要があることを示しています。最初の DFS では、ノードが到達できるすべてのノードを見つけます。逆グラフの dfs は、ノードにアクセスできるすべてのノードを提供します。

完全なコンポーネントを見つけるには、最初の dfs のタイムスタンプに依存することが重要です。

強く連結されたコンポーネントを見つけるための他のアルゴリズムもあり、私の意見では理解しやすいと思います。1 つはkosarajus アルゴリズムです。それを見てください。

私があなたを正しく理解してくれたことを願っています:)

于 2012-11-10T15:44:29.130 に答える