图中最小割线的随机收缩算法

Question

好的，这是我在图中寻找切割的算法(这里我不是在说最小切割)

假设我们得到了一个非有向图的邻接列表。

< li >选择图上的任意顶点(用pivot表示) < li >选择图形上的任何其他顶点(随机)。(用x表示) < li >如果两个顶点之间有一条边，则从图形中删除该边。并将x连接的所有顶点转储到pivot上。(如果不是，则返回步骤2。 < li >如果有任何其他顶点连接到x，则更改邻接表，以便x现在被pivot替换。即它们与枢轴相连。 < li >如果顶点数大于2(返回步骤2) < li >如果等于2。只需计算邻接表中这两个点的顶点数。这将使切割

我的问题是，这个算法正确吗？

Answer 1

同意你一定要去除自循环。我想补充的另一点是，在你随机选择第一个顶点后，你不必随机选择另一个节点，直到你有一个节点连接到第一个节点，你可以简单地从连接到第一个顶点的节点中选择，因为你知道第一个选择的节点连接到多少个节点。所以在更小的范围内进行第二次随机选择。这只是有效地随机选择一条边(由两个节点/顶点决定)。我有一些实现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);
    }
}

}

Answer 2

我只会改变你的随机化。

选择第一个顶点后，从邻接列表中选择另一个顶点。现在，您确定两个顶点之间有边。下一步是从邻接列表中查找顶点。

Answer 3

这是对Krager的无向图的Min-Cut算法的一个很好的解释。

我想你可能错过了一个细节。或者也许我只是误读了你的描述。

< b >您想要移除所有自循环。

例如，在您删除一个顶点并运行您的算法后，顶点A现在可能有一条从顶点A到顶点A的边，这称为自循环。并且它们经常在收缩两个顶点的过程中产生。作为第一步，您可以简单地检查整个图中的自循环，尽管还有一些更复杂的方法。

这有意义吗？