4

さて、これがグラフのカットを見つけるための私のアルゴリズムです（ここでは最小カットについて話していません）

無向グラフの隣接リストが与えられたとしましょう。

  1. グラフ上の任意の頂点を選択します（これをピボットで示します）
  2. グラフ上の他の頂点を（ランダムに）選択します。（これをxで表します）
  3. 2つの頂点の間にエッジがある場合は、そのエッジをグラフから削除します。そして、xが接続されているすべての頂点をピボットにダンプします。（そうでない場合は、ステップ2に戻ります。
  4. 他の頂点がxに接続されている場合は、隣接リストを変更して、xがピボットに置き換えられるようにします。つまり、それらはPivotに接続されています。
  5. 頂点の数が2より大きい場合（ステップ2に戻ります）
  6. 2に等しい場合は、2つのポイントのいずれかの隣接リストに存在する頂点の数を数えます。これはカットを与えます

私の質問は、このアルゴリズムは正しいですか？

4

3 に答える 3

1

これは、無向グラフに対するKragerのMin-Cutアルゴリズムの良い説明です。

あなたが見逃した詳細が1つあるかもしれないと思います。または、おそらく私はあなたの説明を読み間違えました。

すべての自己ループを削除したいとします。

たとえば、頂点を削除してアルゴリズムを実行した後、頂点Aには頂点Aから頂点Aに向かうエッジがある場合があります。これは自己ループと呼ばれます。そして、それらは2つの頂点を縮小する過程で頻繁に生成されます。最初のステップとして、グラフ全体で自己ループを確認するだけですが、より高度なアプローチがいくつかあります。

それは理にかなっていますか？

于 2012-04-09T06:03:02.030 に答える
1

ランダム化のみを変更します。

最初の頂点を選択した後、隣接リストから別の頂点を選択します。これで、2つの頂点の間にエッジがあることを確認できます。次のステップは、調整リストから頂点を見つけることです。

于 2013-07-28T01:02:57.073 に答える
-1

セルフループを確実に削除する必要があることに同意します。また、最初の頂点をランダムに選択した後、最初のノードに接続されているノードができるまで、別のノードをランダムに選択する必要はありません。接続されているノードから選択するだけです。最初に選択されたノードが接続するノードの数がわかっているため、最初の頂点。したがって、より狭い範囲内の2番目のランダムな選択。これは、事実上ランダムにエッジを選択することです（2つのノード/頂点によって決定されます）。私はあなたが遊ぶことができるkragerのアルゴリズムを実装するいくつかのc＃コードを持っています。200ノードのグラフでテストしたため、これは最も効率的なコードではありません（特に、より効率的なデータ構造を使用できます）。10000回の反復では、実行に約30秒かかります。

using System;
using System.Collections.Generic;
using System.Linq;

namespace MinCut
{
    internal struct Graph
    {
        public int N { get; private set; }
        public readonly List<int> Connections;
        public Graph(int n) : this()
        {
            N = n;
            Connections = new List<int>();
        }

    public override bool Equals(object obj)
    {
        return Equals((Graph)obj);
    }

    public override int GetHashCode()
    {
        return base.GetHashCode();
    }

    private bool Equals(Graph g)
    {
        return N == g.N;
    }
}

internal sealed class GraphContraction
{
    public static void Run(IList<Graph> graphs, int i)
    {
        var liveGraphs = graphs.Count;
        if (i >= liveGraphs)
        {
            throw new Exception("Wrong random index generation; index cannot be larger than the number of nodes");
        }
        var leftV = graphs[i];

        var r = new Random();
        var index = r.Next(0, leftV.Connections.Count);
        var rightV = graphs.Where(x=>x.N == leftV.Connections[index]).Single();

        foreach (var v in graphs.Where(x => !x.Equals(leftV) && x.Connections.Contains(leftV.N))) 
        {
            v.Connections.RemoveAll(x => x == leftV.N);
        }
        foreach (var c in leftV.Connections)
        {
            if (c != rightV.N)
            {
                rightV.Connections.Add(c);
                int c1 = c;
                graphs.Where(x=> x.N == c1).First().Connections.Add(rightV.N);
            }
        }
        graphs.Remove(leftV);
    }
}

}

于 2014-11-07T17:15:10.527 に答える