0

私の本では、有向グラフの強連結成分を線形時間で見つける方法を定義しています。さらに、強連結成分を見つけるための他のいくつかのアルゴリズム (つまり、Tarjan のアルゴリズム) も線形時間で成分を見つけることができます。

ただし、これらのアルゴリズムはすべて、ポスト値 (頂点が残っている時間) が減少するようにグラフの頂点を並べ替える必要があります。Mergesort などの一般的な順序付けアルゴリズムは、O(n log n) 時間かかります。

したがって、ポスト値で頂点のリストを並べ替えるのに O(n log n) の時間がかかる場合、これらのアルゴリズムはどのようにして強連結成分の位置を線形時間で完全に特定できるのでしょうか?

4

1 に答える 1

2

「時間」(投稿値が測定される種類) は、時間 (深さ優先探索プログラムによって実行されるステップの数) の関数として単調に非減少であるため、各ノードをリストの直後に追加するだけで十分です。トラバーサルはそれを残します。走査の最後に、リストはソートされた順序になっています。

別の方法として、ポスト値は多項式の上に制限された整数であるため、一部のマシン モデルでは基数ソートなどを使用して線形時間でソートすることができます。

于 2012-06-19T03:28:09.060 に答える