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() 吗?
还是我的算法编码不正确,因此没有正确输出的机会?
注意:试图将此问题标记为作业..找不到标签。