アークによるトポロジカルな並べ替え

アークの定義によるトポロジカルソート（私の質問から） - 方向性グラフのすべてのアークを順序付けする方法です。頂点に挿入するすべてのアークは、来る前にアークする必要がありますこの頂点から外に出る。アークによるトポロジカルな並べ替え

2012-03-25 Nusha

トポロジカルソートでは何も変更する必要はありません。使用するだけで後処理できます。

高レベル疑似コード：

ラントポロジカルソート、結果の配列はarr
がarrの各頂点vためl
ことせ、空のエッジリストを作成することせ[反復を注文] ：
3.1。それぞれ(v,u)をEに：
3.1.1。リターン(v,u) to l
l

を追加し、この方法の利点は、あなたがそれ、ちょうどポストプロセスは、望ましい結果を得るために修正することなく、トポロジカルソートなどのブラックボックスを使用することができます。

正し [証明のスケッチ]：
以来(v,u)各エッジについて - uは、トポロジカルソートでvした後、あなたはそれを印刷するとき、それはvを介して行われ、そしてあなたが任意の頂点を印刷する前に、これ(v,u)が印刷されて表示されますuに添付されています。

複雑：
O(|V|+|E|)トポロジカルソート、後処理のためにO(|V|+|E|) [すべての頂点および全ての辺を反復]。

出典

2012-03-25 22:30:35 amit

ええ、ビッグオーは同じですが、仕事の量を2倍にしなければなりません。 – tchap

@OndrejKupka：確かに、定数はトポロジカルソートを変更しても高くなります。 **トポロジカルソートをカプセル化する**メリットのために。 [これは非常に重要な側面です！]実生活のアプリケーションでは、*この部分がホットスポット*であることが判明した場合は、おそらくそれを書き直したいと思うでしょう。 – amit

はい、それほど多くのコードをコピーするのは実際的ではありません。 – tchap

"従来の"トポロジカルソートは頂点をソートしますが、これはアークをソートします。それ以外の場合、原則は同じです...

出典

2012-03-25 21:59:08 tchap

私はトポロジカルソートアルゴリズムを見ると、アークに対してどのように変更できるのか分かりません... あなたは私のためにそれを解決したくありませんが、私はいくつかの指導をお願いします。 – Nusha

wikiへ移動あなたが渡したページ、opcodeセクション。「nをLに挿入する」と「グラフからエッジeを除去する」というステップでも、「エッジeをLに挿入する」。この方法で、頂点の代わりに円弧を覚えていきます。 – tchap

アークによるトポロジカルな並べ替え

答えて

関連する問題