問題タブ [sink-vertex]

質問する

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

3 問題
Newest
Active
Bountied
318
Unanswered
0 投票する
7 に答える
17164 参照

algorithm - グラフ: O(|V|) 未満でシンクを見つける - またはそれができないことを示す

隣接行列nとしてノードを持つグラフがあります。

シンクを短時間で検出することは可能O(n)ですか?

はいの場合、どのように？いいえの場合、それをどのように証明しますか?

シンク頂点は、他のノードからの入力エッジを持ち、出力エッジを持たない頂点です。

0 投票する
3 に答える
6193 参照

algorithm - 有向非巡回グラフでのシンクの検出

DAG：に次のプロパティを持つ頂点が1つあるとしましょう。

  1. すべての頂点がそれに接続されています

  2. どの頂点にも接続されていません

これは通常、シンク頂点と呼ばれます。

でこの頂点を検出することは可能ですか？グラフの頂点の数はO(n)どこですか？n


12345678910