// Prim2 algorithm calculate minimum spanning tree on the input undirected graph
// Note that MinHeap in this implmenetation is implemented by myself.
Prim2 algorithm calculate minimum spanning tree on the input undirected graph
Note that MinHeap in this implmenetation is implemented by myself.
// Prim2 algorithm calculate minimum spanning tree on the input undirected graph // Note that MinHeap in this implmenetation is implemented by myself .
func Prim2(g weightedgraph.WeightedGraph) (MinSpanningTree, error) {
	mst := MinSpanningTree{[]graph.EdgeID{}, g}
	queringHeap := &myQueryHeap{myMinBinaryHeap{}, map[graph.NodeID]*heapNode{}}
	g.IterateAllNodes(func(u graph.NodeID) {
		item := &heapNode{self: u, parent: graph.InvalidNodeID, key: maxKey}
		queringHeap.insert(item)
		queringHeap.nodeToItem[u] = item
	})
	queringHeap.decreaseKey(queringHeap.nodeToItem[0], 0) 
	for queringHeap.Len() > 0 {
		uItem := queringHeap.extractMin() 
		if uItem.parent != graph.InvalidNodeID {
			mst.edges = append(mst.edges, graph.EdgeID{From: uItem.parent, To: uItem.self})
		}
		g.IterateAdjacencyNodes(uItem.self, func(v graph.NodeID) {
			item, ok := queringHeap.find(v)
			uvWeight, _ := g.Weight(uItem.self, v)
			if ok && uvWeight < item.key {
				queringHeap.decreaseKey(item, uvWeight)
			}
		})
	}
	return mst, nil
}
func Prim2 ( g weightedgraph . WeightedGraph ) ( MinSpanningTree , error ) { mst := MinSpanningTree { [ ] graph . EdgeID { } , g } queringHeap := & myQueryHeap { myMinBinaryHeap { } , map [ graph . NodeID ] * heapNode { } } g . IterateAllNodes ( func ( u graph . NodeID ) { item := & heapNode { self : u , parent : graph . InvalidNodeID , key : maxKey } queringHeap . insert ( item ) queringHeap . nodeToItem [ u ] = item } ) queringHeap . decreaseKey ( queringHeap . nodeToItem [ 0 ] , 0 ) for queringHeap . Len ( ) > 0 { uItem := queringHeap . extractMin ( ) if uItem . parent != graph . InvalidNodeID { mst . edges = append ( mst . edges , graph . EdgeID { From : uItem . parent , To : uItem . self } ) } g . IterateAdjacencyNodes ( uItem . self , func ( v graph . NodeID ) { item , ok := queringHeap . find ( v ) uvWeight , _ := g . Weight ( uItem . self , v ) if ok && uvWeight < item . key { queringHeap . decreaseKey ( item , uvWeight ) } } ) } return mst , nil }
Prim2 algorithm calculate minimum spanning tree on the input undirected graph
Note that MinHeap in this implmenetation is implemented by myself.
Prim2 algorithm calculate minimum spanning tree on the input undirected graph Note that MinHeap in this implmenetation is implemented by myself .
// initialize for queryHeap // random starting node // iterate all nodes by decreasing key //pop min key node