Documentation
¶
Overview ¶
Package mst computes minimum spanning tree for undirected edge-weighted graph. Weight represents a cost (or time) that it takes to propagate through the edge (airline map where weights are distances or fares). Minimizing the cost is naturally of interest in such situations.
A spanning tree of a graph is a connected subgraph with no cycles that includes all the vertices. A min spanning tree (MST) of a graph is a spanning tree whose weights (sum) is no larger than weight of any other spanning tree.
A cut of a graph is a partition of its vertices into two nonempty disjoint sets. A crossing edge of a cut is an edge that connects a vertex in one set with a vertex in the other. Min-weight crossing edge must be in the MST.
The cut property is the basis for Prim's and Kruskal's algorithms for the MST problem. They are special cases of a general paradigm known as greedy algorithm: apply the cut property to accept an edge as an MST edge, continuing until finding all of the MST edges.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AdjacencyList ¶
type AdjacencyList struct {
// contains filtered or unexported fields
}
AdjacencyList maintains a vertex-indexed array of adjacency lists of edges.
func NewAdjacencyList ¶
func NewAdjacencyList(vertices int) *AdjacencyList
NewAdjacencyList creates a graph represented as an array of adjacency lists.
func (*AdjacencyList) Add ¶
func (g *AdjacencyList) Add(e *Edge)
Add adds a new edge connecting v and w vertices.
func (*AdjacencyList) Adjacent ¶
func (g *AdjacencyList) Adjacent(v int) []*Edge
Adjacent returns edges incident to vertex v.
func (*AdjacencyList) EdgeCount ¶
func (g *AdjacencyList) EdgeCount() int
EdgeCount returns number of edges in the graph.
func (*AdjacencyList) Edges ¶
func (g *AdjacencyList) Edges() []*Edge
Edges returns all edges in this graph.
func (*AdjacencyList) VertexCount ¶
func (g *AdjacencyList) VertexCount() int
VertexCount returns number of vertices in the graph.
type Edge ¶
Edge represents graph's edge.
func (*Edge) Either ¶
Either returns either of this edge's vertices. This is useful when neither vertex is known, a client can use the idiomatic code v, w = e.Either(), e.Other(v) to access an edge's two vertices.
type Kruskal ¶
type Kruskal struct {
// contains filtered or unexported fields
}
Kruskal is an implementation of Kruskal's algorithm which uses priority queue to hold edges not yet examined, and a union-find data structure for identifying ineligible edges.
func NewKruskal ¶
func NewKruskal(g *AdjacencyList) *Kruskal
NewKruskal processes the edges in order of their weight (smallest to largest), taking for the MST each edge that doesn't form a cycle with edges previously added, stopping after adding V-1 edges. The edges form a forest of trees that evolves gradually into a single tree, the MST.
Kruskal's algorithm uses space proportional to E and time proportional to E * log E in the worst case. The cost bound is conservative, since the algorithm terminates after finding V-1 MST edges. Kruskal's algorithm is generally slower than Prim's because it has to do a connected operation for each edge.
Example ¶
g := NewAdjacencyList(8)
g.Add(&Edge{V: 4, W: 5, Weight: 0.35})
g.Add(&Edge{V: 4, W: 7, Weight: 0.37})
g.Add(&Edge{V: 5, W: 7, Weight: 0.28})
g.Add(&Edge{V: 0, W: 7, Weight: 0.16})
g.Add(&Edge{V: 1, W: 5, Weight: 0.32})
g.Add(&Edge{V: 0, W: 4, Weight: 0.38})
g.Add(&Edge{V: 2, W: 3, Weight: 0.17})
g.Add(&Edge{V: 1, W: 7, Weight: 0.19})
g.Add(&Edge{V: 0, W: 2, Weight: 0.26})
g.Add(&Edge{V: 1, W: 2, Weight: 0.36})
g.Add(&Edge{V: 1, W: 3, Weight: 0.29})
g.Add(&Edge{V: 2, W: 7, Weight: 0.34})
g.Add(&Edge{V: 6, W: 2, Weight: 0.40})
g.Add(&Edge{V: 3, W: 6, Weight: 0.52})
g.Add(&Edge{V: 6, W: 0, Weight: 0.58})
g.Add(&Edge{V: 6, W: 4, Weight: 0.93})
mst := NewKruskal(g)
for _, e := range mst.Edges() {
fmt.Println(e)
}
fmt.Printf("%.5f", mst.Weight())
Output: 0-7 0.16000 2-3 0.17000 1-7 0.19000 0-2 0.26000 5-7 0.28000 4-5 0.35000 6-2 0.40000 1.81000
type LazyPrim ¶
type LazyPrim struct {
// contains filtered or unexported fields
}
LazyPrim is a lazy version of Prim's algorithm to compute MST. It uses space proportional to E (number of edges) and time proportional to E * log E in the worst case. The bottleneck is the number of edge-weighted comparisons in the priority queue methods insert and delete min. In practice, the upper bound on the running time is a bit conservative because the number of edges on the priority queue is typically much less than E.
func NewLazyPrim ¶
func NewLazyPrim(g *AdjacencyList) *LazyPrim
NewLazyPrim computes MST using Prim's algorithm: take an edge from the priority queue and (if it is eligible) add it to the tree, and also add to the tree the new vertex that it leads to, updating the set of crossing edges by calling visit with that vertex as argument.
This implementation is a lazy approach where ineligible edges are left in the priority queue.
Example ¶
g := NewAdjacencyList(8)
g.Add(&Edge{V: 4, W: 5, Weight: 0.35})
g.Add(&Edge{V: 4, W: 7, Weight: 0.37})
g.Add(&Edge{V: 5, W: 7, Weight: 0.28})
g.Add(&Edge{V: 0, W: 7, Weight: 0.16})
g.Add(&Edge{V: 1, W: 5, Weight: 0.32})
g.Add(&Edge{V: 0, W: 4, Weight: 0.38})
g.Add(&Edge{V: 2, W: 3, Weight: 0.17})
g.Add(&Edge{V: 1, W: 7, Weight: 0.19})
g.Add(&Edge{V: 0, W: 2, Weight: 0.26})
g.Add(&Edge{V: 1, W: 2, Weight: 0.36})
g.Add(&Edge{V: 1, W: 3, Weight: 0.29})
g.Add(&Edge{V: 2, W: 7, Weight: 0.34})
g.Add(&Edge{V: 6, W: 2, Weight: 0.40})
g.Add(&Edge{V: 3, W: 6, Weight: 0.52})
g.Add(&Edge{V: 6, W: 0, Weight: 0.58})
g.Add(&Edge{V: 6, W: 4, Weight: 0.93})
mst := NewLazyPrim(g)
for _, e := range mst.Edges() {
fmt.Println(e)
}
fmt.Printf("%.5f", mst.Weight())
Output: 0-7 0.16000 1-7 0.19000 0-2 0.26000 2-3 0.17000 5-7 0.28000 4-5 0.35000 6-2 0.40000 1.81000
Source Files