0 
   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());
    }

//input.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)]

上記のアルゴリズムは、数回実行して乱数化しても正しい出力が得られません。

ランダムなエッジの選択はどういうわけか歪んでいますか?

代わりに cuts.Add(graph.Vertices.first().count() を実行する必要がありますか?

または、私のアルゴリズムが正しくコーディングされていないため、正しい出力の可能性はありませんか?

注: この質問を宿題としてマークしようとしました..タグが見つかりませんでした。

4

2 に答える 2

0

ブロック間違えたみたい

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

を に変更しif(!Vertices[firstVertex].Contains(edge))ますwhile(!Vertices[firstVertex].Contains(edge))。そうしないと、置換は 1 回だけ行われます。

于 2018-03-28T18:22:02.290 に答える