-
Notifications
You must be signed in to change notification settings - Fork 0
/
LazyPrimMinimumSpanTree.cs
53 lines (48 loc) · 1.43 KB
/
LazyPrimMinimumSpanTree.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using System.Collections.Generic;
using Books.Algorithms.Chap2;
namespace Books.Algorithms.Chap4 {
public class LazyPrimMinimumSpanTree {
private bool[] marked;
private Queue<Edge> mst;
private MinPriorityQueue<Edge> pq;
public LazyPrimMinimumSpanTree(EdgeWeightedGraph g) {
pq = new MinPriorityQueue<Edge>(g.Ecount);
marked = new bool[g.Vcount];
mst = new Queue<Edge>();
Visit(g, 0);
while (!pq.IsEmpty()) {
var e = pq.DelMin();
int v = e.Either;
int w = e.Other(v);
if (marked[v] && marked[w]) {
continue;
}
mst.Enqueue(e);
if (!marked[v]) {
Visit(g, v);
}
if (!marked[w]) {
Visit(g, w);
}
}
}
private void Visit(EdgeWeightedGraph g, int v) {
marked[v] = true;
foreach (var e in g.Adj(v)) {
if (!marked[e.Other(v)]) {
pq.Insert(e);
}
}
}
public IEnumerable<Edge> Edges() {
return mst;
}
public double Weight() {
double weight = 0;
foreach (var e in Edges()) {
weight += e.Weight;
}
return weight;
}
}
}