pgm16_18.txt

来自「c#版本 算法大全 几乎所有常见的算法 This file contain」· 文本 代码 · 共 47 行

//
//   This file contains the C# code from Program 16.18 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C#"
//   by Bruno R. Preiss.
//
//   Copyright (c) 2001--2002 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.brpreiss.com/books/opus6/programs/pgm16_18.txt
//
public class Algorithms
{
    public static Graph KruskalsAlgorithm(Graph g)
    {
	int n = g.NumberOfVertices;

	Graph result = new GraphAsLists(n);
	for (int v = 0; v < n; ++v)
	    result.AddVertex(v);

	PriorityQueue queue =
	    new BinaryHeap(g.NumberOfEdges);
	foreach (Edge e in g.Edges)
	{
	    int weight = (int)e.Weight;
	    queue.Enqueue(new Association(weight, e));
	}

	Partition partition = new PartitionAsForest(n);
	while (!queue.IsEmpty && partition.Count > 1)
	{
	    Association assoc = (Association)queue.DequeueMin();
	    Edge e = (Edge)assoc.Value;
	    int n0 = e.V0.Number;
	    int n1 = e.V1.Number;
	    Set s = partition.Find(n0);
	    Set t = partition.Find(n1);
	    if (s != t)
	    {
		partition.Join(s, t);
		result.AddEdge(n0, n1);
	    }
	}
	return result;
    }
}