pgm16_17.txt

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

//
//   This file contains the C# code from Program 16.17 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_17.txt
//
public class Algorithms
{
    public static Graph PrimsAlgorithm(Graph g, int s)
    {
	int n = g.NumberOfVertices;
	Entry[] table = new Entry[n];
	for (int v = 0; v < n; ++v)
	    table[v] = new Entry(false,
		int.MaxValue, int.MaxValue);
	table[s].distance = 0;
	PriorityQueue queue = new BinaryHeap(g.NumberOfEdges);
	queue.Enqueue(new Association(0, g.GetVertex(s)));
	while (!queue.IsEmpty)
	{
	    Association assoc = (Association)queue.DequeueMin();
	    Vertex v0 = (Vertex)assoc.Value;
	    if (!table[v0.Number].known)
	    {
		table[v0.Number].known = true;
		foreach (Edge e in v0.EmanatingEdges)
		{
		    Vertex v1 = e.MateOf(v0);
		    int d = (int)e.Weight;
		    if (!table[v1.Number].known &&
			table[v1.Number].distance>d)
		    {
			table[v1.Number].distance = d;
			table[v1.Number].predecessor = v0.Number;
			queue.Enqueue(new Association(d, v1));
		    }
		}
	    }
	}
	Graph result = new GraphAsLists(n);
	for (int v = 0; v < n; ++v)
	    result.AddVertex(v);
	for (int v = 0; v < n; ++v)
	    if (v != s)
		result.AddEdge(v, table[v].predecessor);
	return result;
    }
}