2

グラフ内のすべての頂点のセットを、隣接する頂点よりも小さい次数で見つけるアルゴリズムを作成しようとしています。私の最初のアプローチは、各頂点の次数を見つけてから、リストを調べて、各頂点の次数をその近傍の次数と比較することです。残念ながら、これには非常に時間がかかるようです。このセットを見つけるより効率的な方法はありますか?

4

3 に答える 3

3

1 つのコメント -無向グラフ( Brian R. Bondyに感謝) を使用している場合、頂点の次数がすべての隣接点よりも小さいと判断したら、隣接点をチェックする必要はありません。それらのうちの 1 つがそのプロパティを持ちます。その知識を使ってあなたを助け、物事をスピードアップすることを検討してください.

于 2008-11-13T16:25:34.420 に答える
2

おそらく「これは非常に時間がかかるように見える」かもしれませんが、見つけるためのより良い方法があります:-)

グラフを隣接リストとして保存したとします。探しているセットを見つけるには、必然的にすべてのエッジを調べる必要があるため、アルゴリズムの下限は Ω(|E|) です。すべての頂点の次数を見つけるには O(|E|) の時間がかかります (すべてのエッジを 1 回だけ見るためです。もう 1 つの証明は、∑d(v)=2|E| という事実を使用することです)。各頂点の次数をそのすべての隣接頂点と比較するのにも、O(|E|) 時間しかかかりません (ここでも、エッジごとに 1 回だけ比較を行います)。これは、アルゴリズムが O(|E|) 時間 (約 2|E| の「ステップ」ですが、CPU 命令の正確な数は実装によって異なります) で実行され、下限を満たすことを意味します。したがって、最悪の場合、「ブルートフォース」アルゴリズムは本質的に（小さな定数まで）可能な限り高速ですであるため、これ以上最適化する価値はありません。

実際のアプリケーションでこれを行っていて、実際にアルゴリズムに時間がかかりすぎていることがわかった場合は、プロファイラーを使用して最適化する部分を見つけてください。アルゴリズムの第 2 段階の最適化が重要であることはまったく明らかではありません。

于 2008-11-13T21:37:06.273 に答える
1

次のように、無向グラフに対する貪欲なアプローチを想像します。

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

このアルゴリズムは、反復ごとに満足のいくノードを見つけるか、次数の低い新しいノードをチェックしてグラフからノードを削除するため、わずかに効率的です。

最悪の場合、ブルート フォース アルゴリズムと同等になります。ただし、平均すると、パフォーマンスが向上するはずです。

于 2008-11-13T17:09:40.323 に答える