mst

boruvka.go

// Boruvka's algorithm for Minimum Spanning Tree
func boruvka(graph *Graph) (mst *Graph) {
	mst = NewGraph()
	// set up the MST
	for _, node := range graph.Nodes {
		mst.AddNode(node)
	}

	var subgraphs []*Subgraph
	// set up the subgraphs; intially each subgraph has only 1 node
	for _, node := range graph.Nodes {
		s := &Subgraph{nodes: []*Node{node}}
		for _, edge := range graph.Edges[node.name] {
			s.pairs = append(s.pairs, &NodePair{node, edge})
		}
		subgraphs = append(subgraphs, s)
	}

	// repeatedly combine the subgraphs until there is only 1
	for len(subgraphs) > 1 {
		pairs := subgraphs[0].pairs
		sort.Slice(pairs, func(i, j int) bool {
			return pairs[i].edge.weight < pairs[j].edge.weight
		})
		mst.AddEdge(pairs[0].node, pairs[0].edge.node, pairs[0].edge.weight)
		subgraphs = combine(pairs[0].node, pairs[0].edge.node, subgraphs)
	}

	return
}