sausheong

func (g *Graph) HasEdge(name string, edge *Edge) bool {
	for _, e := range g.Edges[name] {
		if e.node.name == edge.node.name && e.weight == edge.weight {
			return true
		}
	}
	return false
}

sausheong

type Heap []NodePair

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i].edge.weight < h[j].edge.weight }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x any)        { *h = append(*h, x.(NodePair)) }

func (h *Heap) Pop() any {
	old := *h
	n := len(old)

sausheong

// Kruskal's algorithm for Minimum Spanning Tree
func kruskal(graph *Graph) (mst *Graph) {
	mst = NewGraph()
	h := &Heap{}
	heap.Init(h)
	// get a sorted list of edges
	for nodeName, edges := range graph.Edges {
		node := graph.GetNode(nodeName)
		for _, edge := range edges {
			heap.Push(h, NodePair{node, edge})

sausheong

// check if a node is in a subgraph
func in(node *Node, subgraph *Subgraph) bool {
	for _, n := range subgraph.nodes {
		if n.name == node.name {
			return true
		}
	}
	return false
}

sausheong

// combine 2 different subgraphs by connecting 2 nodes
func combine(n1, n2 *Node, subgraphs []*Subgraph) []*Subgraph {
	var s1, s2 *Subgraph
	var i2 int
	for i, subgraph := range subgraphs {
		// find the 2 subgraphs which has the 2 nodes
		for _, node := range subgraph.nodes {
			if n1.name == node.name {
				s1 = subgraph
			}

sausheong

type NodePair struct {
	node *Node
	edge *Edge
}

sausheong

// 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

sausheong

type Subgraph struct {
	nodes []*Node
	pairs []*NodePair
}

sausheong

func main() {
	graph := buildGraph()
	fmt.Println("GRAPH\n-----")
	nodes := sortNodes(graph.Nodes)
	for _, node := range nodes {
		fmt.Printf("%s -> %v\n", node.name, graph.Edges[node.name])
	}
 }

sausheong

func buildGraph() *Graph {
	graph := NewGraph()
	nodes := make(map[string]*Node)
	for _, name := range []string{"A", "B", "C", "D", "E", "F", "G"} {
		n := &Node{name, 0}
		graph.AddNode(n)
		nodes[name] = n
	}

	graph.AddEdge(nodes["A"], nodes["B"], 7)