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

	// A = ∅
	A := make(map[Edge]struct{})

	// disjointSet maps a member Node to a represent.
	// (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
	forests := NewForests()

	// for each vertex v in G:
	for _, nd := range g.GetNodes() {
		// MakeDisjointSet(v)
		MakeDisjointSet(forests, nd.String())
	}

	// edges = get all edges
	edges := []Edge{}
	foundEdge := make(map[string]struct{})
	for id1, nd1 := range g.GetNodes() {
		tm, err := g.GetTargets(id1)
		if err != nil {
			return nil, err
		}
		for id2, nd2 := range tm {
			weight, err := g.GetWeight(id1, id2)
			if err != nil {
				return nil, err
			}
			edge := NewEdge(nd1, nd2, weight)
			if _, ok := foundEdge[edge.String()]; !ok {
				edges = append(edges, edge)
				foundEdge[edge.String()] = struct{}{}
			}
		}

		sm, err := g.GetSources(id1)
		if err != nil {
			return nil, err
		}
		for id3, nd3 := range sm {
			weight, err := g.GetWeight(id3, id1)
			if err != nil {
				return nil, err
			}
			edge := NewEdge(nd3, nd1, weight)
			if _, ok := foundEdge[edge.String()]; !ok {
				edges = append(edges, edge)
				foundEdge[edge.String()] = struct{}{}
			}
		}
	}

	// sort edges in ascending order of weight
	sort.Sort(EdgeSlice(edges))

	// for each edge (u, v) in edges:
	for _, edge := range edges {
		// if FindSet(u) ≠ FindSet(v):
		if FindSet(forests, edge.Source().String()).represent != FindSet(forests, edge.Target().String()).represent {

			// A = A ∪ {(u, v)}
			A[edge] = struct{}{}

			// Union(u, v)
			// overwrite v's represent with u's represent
			Union(forests, FindSet(forests, edge.Source().String()), FindSet(forests, edge.Target().String()))
		}
	}

	return A, nil
}
func Kruskal(g Graph) (map[Edge]struct{}, error) {

	// A = ∅
	A := make(map[Edge]struct{})

	// disjointSet maps a member Node to a represent.
	// (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
	forests := NewForests()

	// for each vertex v in G:
	for _, nd := range g.GetNodes() {
		// MakeDisjointSet(v)
		MakeDisjointSet(forests, nd.String())
	}

	// edges = get all edges
	edges := []Edge{}
	foundEdge := make(map[string]struct{})
	for id1, nd1 := range g.GetNodes() {
		tm, err := g.GetTargets(id1)
		if err != nil {
			return nil, err
		}
		for id2, nd2 := range tm {
			weight, err := g.GetWeight(id1, id2)
			if err != nil {
				return nil, err
			}
			edge := NewEdge(nd1, nd2, weight)
			if _, ok := foundEdge[edge.String()]; !ok {
				edges = append(edges, edge)
				foundEdge[edge.String()] = struct{}{}
			}
		}

		sm, err := g.GetSources(id1)
		if err != nil {
			return nil, err
		}
		for id3, nd3 := range sm {
			weight, err := g.GetWeight(id3, id1)
			if err != nil {
				return nil, err
			}
			edge := NewEdge(nd3, nd1, weight)
			if _, ok := foundEdge[edge.String()]; !ok {
				edges = append(edges, edge)
				foundEdge[edge.String()] = struct{}{}
			}
		}
	}

	// sort edges in ascending order of weight
	sort.Sort(EdgeSlice(edges))

	// for each edge (u, v) in edges:
	for _, edge := range edges {
		// if FindSet(u) ≠ FindSet(v):
		if FindSet(forests, edge.Source().String()).represent != FindSet(forests, edge.Target().String()).represent {

			// A = A ∪ {(u, v)}
			A[edge] = struct{}{}

			// Union(u, v)
			// overwrite v's represent with u's represent
			Union(forests, FindSet(forests, edge.Source().String()), FindSet(forests, edge.Target().String()))
		}
	}

	return A, nil
}
func Kruskal ( g Graph ) ( map [ Edge ] struct { } , error ) { // A = ∅ A := make ( map [ Edge ] struct { } ) // disjointSet maps a member Node to a represent. // (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) forests := NewForests ( ) // for each vertex v in G: for _ , nd := range g . GetNodes ( ) { // MakeDisjointSet(v) MakeDisjointSet ( forests , nd . String ( ) ) } // edges = get all edges edges := [ ] Edge { } foundEdge := make ( map [ string ] struct { } ) for id1 , nd1 := range g . GetNodes ( ) { tm , err := g . GetTargets ( id1 ) if err != nil { return nil , err } for id2 , nd2 := range tm { weight , err := g . GetWeight ( id1 , id2 ) if err != nil { return nil , err } edge := NewEdge ( nd1 , nd2 , weight ) if _ , ok := foundEdge [ edge . String ( ) ] ; ! ok { edges = append ( edges , edge ) foundEdge [ edge . String ( ) ] = struct { } { } } } sm , err := g . GetSources ( id1 ) if err != nil { return nil , err } for id3 , nd3 := range sm { weight , err := g . GetWeight ( id3 , id1 ) if err != nil { return nil , err } edge := NewEdge ( nd3 , nd1 , weight ) if _ , ok := foundEdge [ edge . String ( ) ] ; ! ok { edges = append ( edges , edge ) foundEdge [ edge . String ( ) ] = struct { } { } } } } // sort edges in ascending order of weight sort . Sort ( EdgeSlice ( edges ) ) // for each edge (u, v) in edges: for _ , edge := range edges { // if FindSet(u) ≠ FindSet(v): if FindSet ( forests , edge . Source ( ) . String ( ) ) . represent != FindSet ( forests , edge . Target ( ) . String ( ) ) . represent { // A = A ∪ {(u, v)} A [ edge ] = struct { } { } // Union(u, v) // overwrite v's represent with u's represent Union ( forests , FindSet ( forests , edge . Source ( ) . String ( ) ) , FindSet ( forests , edge . Target ( ) . String ( ) ) ) } } return A , nil }
// Kruskal finds the minimum spanning tree with disjoint-set data structure.
// (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
//
//	 0. Kruskal(G)
//	 1.
//	 2. 	A = ∅
//	 3.
//	 4. 	for each vertex v in G:
//	 5. 		MakeDisjointSet(v)
//	 6.
//	 7. 	edges = get all edges
//	 8. 	sort edges in ascending order of weight
//	 9.
//	10. 	for each edge (u, v) in edges:
//	11. 		if FindSet(u) ≠ FindSet(v):
//	12. 			A = A ∪ {(u, v)}
//	13. 			Union(u, v)
//	14.
//	15. 	return A
//
Kruskal finds the minimum spanning tree with disjoint - set data structure . ( http : // en . wikipedia . org / wiki / Kruskal%27s_algorithm ) 0 . Kruskal ( G ) 1 . 2 . A = ∅ 3 . 4 . for each vertex v in G : 5 . MakeDisjointSet ( v ) 6 . 7 . edges = get all edges 8 . sort edges in ascending order of weight 9 . 10 . for each edge ( u v ) in edges : 11 . if FindSet ( u ) ≠ FindSet ( v ) : 12 . A = A ∪ { ( u v ) } 13 . Union ( u v ) 14 . 15 . return A