26 using System.Collections.Generic;
55 public sealed
class Prim<TCost>
56 where TCost : IComparable<TCost>
58 public IGraph Graph {
get;
private set; }
59 public Func<Arc, TCost> Cost {
get;
private set; }
62 public HashSet<Arc> Forest {
get;
private set; }
64 public Prim(
IGraph graph, Func<Arc, TCost> cost)
68 Forest =
new HashSet<Arc>();
76 PriorityQueue<Node, TCost> priorityQueue =
new PriorityQueue<Node, TCost>();
77 HashSet<Node> processed =
new HashSet<Node>();
78 Dictionary<Node, Arc> parentArc =
new Dictionary<Node, Arc>();
82 foreach (var c
in components.Components)
84 Node root = c.First();
86 foreach (var arc
in Graph.Arcs(root))
88 Node v = Graph.Other(arc, root);
90 priorityQueue[v] = Cost(arc);
95 while (priorityQueue.Count != 0)
97 Node n = priorityQueue.Peek();
100 Forest.Add(parentArc[n]);
102 foreach (var arc
in Graph.Arcs(n))
105 if (processed.Contains(v))
continue;
107 TCost arcCost = Cost(arc);
108 if (arcCost.CompareTo(priorityQueue[v]) < 0)
110 priorityQueue[v] = arcCost;
139 public sealed
class Kruskal<TCost>
140 where TCost : IComparable<TCost>
143 public IGraph Graph {
get;
private set; }
145 public Func<Arc, TCost> Cost {
get;
private set; }
151 public Func<Node, int> MaxDegree {
get;
private set; }
156 public HashSet<Arc> Forest {
get;
private set; }
158 public Dictionary<Node, int> Degree {
get;
private set; }
160 private IEnumerator<Arc> arcEnumerator;
161 private int arcsToGo;
162 private DisjointSet<Node> components;
164 public Kruskal(
IGraph graph, Func<Arc, TCost> cost, Func<Node, int> maxDegree = null)
168 MaxDegree = maxDegree;
170 Forest =
new HashSet<Arc>();
171 Degree =
new Dictionary<Node, int>();
172 foreach (var node
in Graph.Nodes()) Degree[node] = 0;
174 List<Arc> arcs = Graph.Arcs().ToList();
175 arcs.Sort((a, b) => Cost(a).CompareTo(Cost(b)));
176 arcEnumerator = arcs.GetEnumerator();
178 components =
new DisjointSet<Node>();
186 if (arcsToGo <= 0 || arcEnumerator == null || !arcEnumerator.MoveNext())
188 arcEnumerator = null;
192 AddArc(arcEnumerator.Current);
206 public bool AddArc(
Arc arc)
208 var u = Graph.U(arc);
209 if (MaxDegree != null && Degree[u] >= MaxDegree(u))
return false;
210 DisjointSetSet<Node> x = components.WhereIs(u);
212 var v = Graph.V(arc);
213 if (MaxDegree != null && Degree[v] >= MaxDegree(v))
return false;
214 DisjointSetSet<Node> y = components.WhereIs(v);
216 if (x == y)
return false;
219 components.Union(x, y);