minimum_spanning_tree.go
func Prim(g Graph, src ID) (map[Edge]struct{}, error) {

	// let Q be a priority queue
	minHeap := &nodeDistanceHeap{}

	// distance[source] = 0
	distance := make(map[ID]float64)
	distance[src] = 0.0

	// for each vertex v in G:
	for id := range g.GetNodes() {

		// if v ≠ src:
		if id != src {
			// distance[v] = ∞
			distance[id] = math.MaxFloat64

			// prev[v] = undefined
			// prev[v] = ""
		}

		// Q.add_with_priority(v, distance[v])
		nds := nodeDistance{}
		nds.id = id
		nds.distance = distance[id]

		heap.Push(minHeap, nds)
	}

	heap.Init(minHeap)
	prev := make(map[ID]ID)

	// while Q is not empty:
	for minHeap.Len() != 0 {

		// u = Q.extract_min()
		u := heap.Pop(minHeap).(nodeDistance)
		uID := u.id

		// for each adjacent vertex v of u:
		tm, err := g.GetTargets(uID)
		if err != nil {
			return nil, err
		}
		for vID := range tm {

			isExist := false
			for _, one := range *minHeap {
				if vID == one.id {
					isExist = true
					break
				}
			}

			// weight(u, v)
			weight, err := g.GetWeight(uID, vID)
			if err != nil {
				return nil, err
			}

			// if v ∈ Q and distance[v] > weight(u, v):
			if isExist && distance[vID] > weight {

				// distance[v] = weight(u, v)
				distance[vID] = weight

				// prev[v] = u
				prev[vID] = uID

				// Q.decrease_priority(v, weight(u, v))
				minHeap.updateDistance(vID, weight)
				heap.Init(minHeap)
			}
		}

		sm, err := g.GetSources(uID)
		if err != nil {
			return nil, err
		}
		vID := uID
		for uID := range sm {

			isExist := false
			for _, one := range *minHeap {
				if vID == one.id {
					isExist = true
					break
				}
			}

			// weight(u, v)
			weight, err := g.GetWeight(uID, vID)
			if err != nil {
				return nil, err
			}

			// if v ∈ Q and distance[v] > weight(u, v):
			if isExist && distance[vID] > weight {

				// distance[v] = weight(u, v)
				distance[vID] = weight

				// prev[v] = u
				prev[vID] = uID

				// Q.decrease_priority(v, weight(u, v))
				minHeap.updateDistance(vID, weight)
				heap.Init(minHeap)
			}
		}
	}

	tree := make(map[Edge]struct{})
	for k, v := range prev {
		weight, err := g.GetWeight(v, k)
		if err != nil {
			return nil, err
		}
		src, err := g.GetNode(v)
		if err != nil {
			return nil, err
		}
		tgt, err := g.GetNode(k)
		if err != nil {
			return nil, err
		}
		tree[NewEdge(src, tgt, weight)] = struct{}{}
	}
	return tree, nil
}
func Prim(g Graph, src ID) (map[Edge]struct{}, error) {

	// let Q be a priority queue
	minHeap := &nodeDistanceHeap{}

	// distance[source] = 0
	distance := make(map[ID]float64)
	distance[src] = 0.0

	// for each vertex v in G:
	for id := range g.GetNodes() {

		// if v ≠ src:
		if id != src {
			// distance[v] = ∞
			distance[id] = math.MaxFloat64

			// prev[v] = undefined
			// prev[v] = ""
		}

		// Q.add_with_priority(v, distance[v])
		nds := nodeDistance{}
		nds.id = id
		nds.distance = distance[id]

		heap.Push(minHeap, nds)
	}

	heap.Init(minHeap)
	prev := make(map[ID]ID)

	// while Q is not empty:
	for minHeap.Len() != 0 {

		// u = Q.extract_min()
		u := heap.Pop(minHeap).(nodeDistance)
		uID := u.id

		// for each adjacent vertex v of u:
		tm, err := g.GetTargets(uID)
		if err != nil {
			return nil, err
		}
		for vID := range tm {

			isExist := false
			for _, one := range *minHeap {
				if vID == one.id {
					isExist = true
					break
				}
			}

			// weight(u, v)
			weight, err := g.GetWeight(uID, vID)
			if err != nil {
				return nil, err
			}

			// if v ∈ Q and distance[v] > weight(u, v):
			if isExist && distance[vID] > weight {

				// distance[v] = weight(u, v)
				distance[vID] = weight

				// prev[v] = u
				prev[vID] = uID

				// Q.decrease_priority(v, weight(u, v))
				minHeap.updateDistance(vID, weight)
				heap.Init(minHeap)
			}
		}

		sm, err := g.GetSources(uID)
		if err != nil {
			return nil, err
		}
		vID := uID
		for uID := range sm {

			isExist := false
			for _, one := range *minHeap {
				if vID == one.id {
					isExist = true
					break
				}
			}

			// weight(u, v)
			weight, err := g.GetWeight(uID, vID)
			if err != nil {
				return nil, err
			}

			// if v ∈ Q and distance[v] > weight(u, v):
			if isExist && distance[vID] > weight {

				// distance[v] = weight(u, v)
				distance[vID] = weight

				// prev[v] = u
				prev[vID] = uID

				// Q.decrease_priority(v, weight(u, v))
				minHeap.updateDistance(vID, weight)
				heap.Init(minHeap)
			}
		}
	}

	tree := make(map[Edge]struct{})
	for k, v := range prev {
		weight, err := g.GetWeight(v, k)
		if err != nil {
			return nil, err
		}
		src, err := g.GetNode(v)
		if err != nil {
			return nil, err
		}
		tgt, err := g.GetNode(k)
		if err != nil {
			return nil, err
		}
		tree[NewEdge(src, tgt, weight)] = struct{}{}
	}
	return tree, nil
}
func Prim ( g Graph , src ID ) ( map [ Edge ] struct { } , error ) { // let Q be a priority queue minHeap := & nodeDistanceHeap { } // distance[source] = 0 distance := make ( map [ ID ] float64 ) distance [ src ] = 0.0 // for each vertex v in G: for id := range g . GetNodes ( ) { // if v ≠ src: if id != src { // distance[v] = ∞ distance [ id ] = math . MaxFloat64 // prev[v] = undefined // prev[v] = "" } // Q.add_with_priority(v, distance[v]) nds := nodeDistance { } nds . id = id nds . distance = distance [ id ] heap . Push ( minHeap , nds ) } heap . Init ( minHeap ) prev := make ( map [ ID ] ID ) // while Q is not empty: for minHeap . Len ( ) != 0 { // u = Q.extract_min() u := heap . Pop ( minHeap ) . ( nodeDistance ) uID := u . id // for each adjacent vertex v of u: tm , err := g . GetTargets ( uID ) if err != nil { return nil , err } for vID := range tm { isExist := false for _ , one := range * minHeap { if vID == one . id { isExist = true break } } // weight(u, v) weight , err := g . GetWeight ( uID , vID ) if err != nil { return nil , err } // if v ∈ Q and distance[v] > weight(u, v): if isExist && distance [ vID ] > weight { // distance[v] = weight(u, v) distance [ vID ] = weight // prev[v] = u prev [ vID ] = uID // Q.decrease_priority(v, weight(u, v)) minHeap . updateDistance ( vID , weight ) heap . Init ( minHeap ) } } sm , err := g . GetSources ( uID ) if err != nil { return nil , err } vID := uID for uID := range sm { isExist := false for _ , one := range * minHeap { if vID == one . id { isExist = true break } } // weight(u, v) weight , err := g . GetWeight ( uID , vID ) if err != nil { return nil , err } // if v ∈ Q and distance[v] > weight(u, v): if isExist && distance [ vID ] > weight { // distance[v] = weight(u, v) distance [ vID ] = weight // prev[v] = u prev [ vID ] = uID // Q.decrease_priority(v, weight(u, v)) minHeap . updateDistance ( vID , weight ) heap . Init ( minHeap ) } } } tree := make ( map [ Edge ] struct { } ) for k , v := range prev { weight , err := g . GetWeight ( v , k ) if err != nil { return nil , err } src , err := g . GetNode ( v ) if err != nil { return nil , err } tgt , err := g . GetNode ( k ) if err != nil { return nil , err } tree [ NewEdge ( src , tgt , weight ) ] = struct { } { } } return tree , nil }
// Prim finds the minimum spanning tree with min-heap (priority queue).
// (http://en.wikipedia.org/wiki/Prim%27s_algorithm)
//
//	 0. Prim(G, source)
//	 1.
//	 2. 	let Q be a priority queue
//	 3. 	distance[source] = 0
//	 4.
//	 5. 	for each vertex v in G:
//	 6.
//	 7. 		if v ≠ source:
//	 8. 			distance[v] = ∞
//	 9. 			prev[v] = undefined
//	10.
//	11. 		Q.add_with_priority(v, distance[v])
//	12.
//	13.
//	14. 	while Q is not empty:
//	15.
//	16. 		u = Q.extract_min()
//	17.
//	18. 		for each adjacent vertex v of u:
//	19.
//	21. 			if v ∈ Q and distance[v] > weight(u, v):
//	22. 				distance[v] = weight(u, v)
//	23. 				prev[v] = u
//	24. 				Q.decrease_priority(v, weight(u, v))
//	25.
//	26.
//	27. 	return tree from prev
//
Prim finds the minimum spanning tree with min - heap ( priority queue ) . ( http : // en . wikipedia . org / wiki / Prim%27s_algorithm ) 0 . Prim ( G source ) 1 . 2 . let Q be a priority queue 3 . distance [ source ] = 0 4 . 5 . for each vertex v in G : 6 . 7 . if v ≠ source : 8 . distance [ v ] = ∞ 9 . prev [ v ] = undefined 10 . 11 . Q . add_with_priority ( v distance [ v ] ) 12 . 13 . 14 . while Q is not empty : 15 . 16 . u = Q . extract_min () 17 . 18 . for each adjacent vertex v of u : 19 . 21 . if v ∈ Q and distance [ v ] > weight ( u v ) : 22 . distance [ v ] = weight ( u v ) 23 . prev [ v ] = u 24 . Q . decrease_priority ( v weight ( u v )) 25 . 26 . 27 . return tree from prev