在 C# 中使用 Krager 算法求解最小割图

Question

public class Graph
{
    public Graph()
    {
        Vertices = new Dictionary<int, List<int>>();
    }

    public Dictionary<int,List<int>> Vertices { get; set; }

    public void ApplyKrager()
    {
        var random = new Random();
        while (Vertices.Count > 2)
        {
            
            var randomIndex = random.Next(0,Vertices.Keys.Count);
            var firstVertex = Vertices.Keys.ElementAt(randomIndex);
            var secondVertex = Vertices[firstVertex].ElementAt(random.Next(0,Vertices[firstVertex].Count));
            if (Vertices.ContainsKey(secondVertex))
            {
                Console.WriteLine();
                Console.WriteLine("Merging " + firstVertex + " " + secondVertex);
                //Merge
                foreach (var edge in Vertices[secondVertex])
                {
                    if (!Vertices[firstVertex].Contains(edge))
                        Vertices[firstVertex].Add(edge);
                }

                //change all the occurences of the secondVertex to the first
                foreach (var vertex in Vertices)
                {
                    if (vertex.Value.Contains(secondVertex))
                    {
                        vertex.Value.Remove(secondVertex);
                        vertex.Value.Add(firstVertex);
                    }
                }
                //Remove Self Loops
                Vertices[firstVertex].RemoveAll(_ => _ == firstVertex);
                Vertices.Remove(secondVertex);
            }
            //Print();
        }

    }

    public void Print()
    {
        foreach (var v in Vertices)
        {
            Console.WriteLine("Vertex is : " + v.Key);
            Console.Write("Edges are ");
            foreach (var edge in v.Value)
            {
                Console.Write(edge + " ");
            }
            Console.WriteLine();
        }
    }
}

运行此代码的测试

    [Fact]
    public void CheckForMinimumCuts()
    {
          var input = File.ReadAllLines(@"input.txt");
        var directedEdges = new Dictionary<int, List<int>>();
        foreach (var line in input)
        {
            var adjacency = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            var vertex = Convert.ToInt32(adjacency[0]);
            var edges = new List<int>();
            for (int i = 1, j = 0; i < adjacency.Length; i++)
            {
                edges.Add(Convert.ToInt32(adjacency[i]));
            }

            directedEdges.Add(vertex, edges);
        }

        var cuts = new List<int>();
        for (int i = 0; i < 500; i++)
        {
            var graph = new Graph {Vertices = directedEdges};
            graph.ApplyKrager();
            foreach (var v in graph.Vertices)
            {
                cuts.Add(v.Value.Count);
            }
        }

        Console.WriteLine(cuts.Min());
    }

//输入.txt

1 3 4 2
2 1 4 3
3 1 2 4
4 5 3 2 1
5 4 8 6 7
6 8 7 5
7 5 8 6
8 5 7 6

expected result: 1
cut is [(4,5)]

即使运行多次实现随机化，上面的算法也没有给出正确的输出。

我选择的随机边缘是否有某种偏差？

我应该做 cut.Add(graph.Vertices.first().count() 吗？

或者我的算法编码不正确，因此没有机会获得正确的输出？

注意：试图将此问题标记为作业..找不到标签。

Answer 1

随机收缩最小割算法要求您统一随机选择一条边。您均匀随机选择一个顶点，然后均匀随机选择与该顶点相关的边。

您可能还有一个我看不到的实现错误，因为我不懂 C#。如果您的算法在 8 顶点图上进行 500 次迭代未能确定最小割，我会感到惊讶。

new Random()

是否每次都会产生具有相同种子的 RNG？

Answer 2

我认为你在区块中犯了一个错误

//change all the occurences of the secondVertex to the first.              

将

if(!Vertices[firstVertex].Contains(edge))

更改为

while(!Vertices[firstVertex].Contains(edge))

，否则仅替换一次。