Content-Length: 1035780 | pFad | http://github.com/TheAlgorithms/Go/commit/f2de2860f61ba7601ceb2b7fbbcc147b6d34cf7c

2C Feat: Add Union Find Algorithm, Test: Add test for Union Find Algorit… · TheAlgorithms/Go@f2de286 · GitHub
Skip to content

Commit f2de286

Browse files
MugdhaBehereMugdhaBehere
authored
Feat: Add Union Find Algorithm, Test: Add test for Union Find Algorithm (#687)
* feat:Add Union Find(Dynamic Connectivity)Algorithm * test: Add test for Union Find Algorithm * docs: made changes to comment structure * fix: removed an error in the code * fix: removed errors in unionfind_test.go * fix: updata kruskal's algorithm * fix: update kruskal_test.go * fix: updated comments kruskal.go * fix: removed code redundancy * fix: removed main function * fix: changes to code * fix: updated the code * fix: updated code * fix: removed redundant spaces between comments * fix: formatted code with gofmt * fix: updated code * fix: formatted the files again
1 parent e255e17 commit f2de286

File tree

4 files changed

+149
-191
lines changed

4 files changed

+149
-191
lines changed

‎graph/kruskal.go

+23-79
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
// KRUSKAL'S ALGORITHM
2-
// https://cp-algorithms.com/data_structures/disjoint_set_union.html
3-
// https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html
2+
// Reference: Kruskal's Algorithm: https://www.scaler.com/topics/data-structures/kruskal-algorithm/
3+
// Reference: Union Find Algorithm: https://www.scaler.com/topics/data-structures/disjoint-set/
4+
// Author: Author: Mugdha Behere[https://github.com/MugdhaBehere]
5+
// Worst Case Time Complexity: O(E log E), where E is the number of edges.
6+
// Worst Case Space Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
7+
// see kruskal.go, kruskal_test.go
48

59
package graph
610

@@ -10,104 +14,44 @@ import (
1014

1115
type Vertex int
1216

13-
// Edge describes the edge of a weighted graph
1417
type Edge struct {
1518
Start Vertex
1619
End Vertex
1720
Weight int
1821
}
1922

20-
// DisjointSetUnionElement describes what an element of DSU looks like
21-
type DisjointSetUnionElement struct {
22-
Parent Vertex
23-
Rank int
24-
}
25-
26-
// DisjointSetUnion is a data structure that treats its elements as separate sets
27-
// and provides fast operations for set creation, merging sets, and finding the parent
28-
// of the given element of a set.
29-
type DisjointSetUnion []DisjointSetUnionElement
30-
31-
// NewDSU will return an initialised DSU using the value of n
32-
// which will be treated as the number of elements out of which
33-
// the DSU is being made
34-
func NewDSU(n int) *DisjointSetUnion {
35-
36-
dsu := DisjointSetUnion(make([]DisjointSetUnionElement, n))
37-
return &dsu
38-
}
39-
40-
// MakeSet will create a set in the DSU for the given node
41-
func (dsu DisjointSetUnion) MakeSet(node Vertex) {
42-
43-
dsu[node].Parent = node
44-
dsu[node].Rank = 0
45-
}
46-
47-
// FindSetRepresentative will return the parent element of the set the given node
48-
// belongs to. Since every single element in the path from node to parent
49-
// has the same parent, we store the parent value for each element in the
50-
// path. This reduces consequent function calls and helps in going from O(n)
51-
// to O(log n). This is known as path compression technique.
52-
func (dsu DisjointSetUnion) FindSetRepresentative(node Vertex) Vertex {
53-
54-
if node == dsu[node].Parent {
55-
return node
56-
}
57-
58-
dsu[node].Parent = dsu.FindSetRepresentative(dsu[node].Parent)
59-
return dsu[node].Parent
60-
}
61-
62-
// unionSets will merge two given sets. The naive implementation of this
63-
// always combines the secondNode's tree with the firstNode's tree. This can lead
64-
// to creation of trees of length O(n) so we optimize by attaching the node with
65-
// smaller rank to the node with bigger rank. Rank represents the upper bound depth of the tree.
66-
func (dsu DisjointSetUnion) UnionSets(firstNode Vertex, secondNode Vertex) {
67-
68-
firstNode = dsu.FindSetRepresentative(firstNode)
69-
secondNode = dsu.FindSetRepresentative(secondNode)
70-
71-
if firstNode != secondNode {
72-
73-
if dsu[firstNode].Rank < dsu[secondNode].Rank {
74-
firstNode, secondNode = secondNode, firstNode
75-
}
76-
dsu[secondNode].Parent = firstNode
77-
78-
if dsu[firstNode].Rank == dsu[secondNode].Rank {
79-
dsu[firstNode].Rank++
80-
}
81-
}
82-
}
83-
84-
// KruskalMST will return a minimum spanning tree along with its total cost
85-
// to using Kruskal's algorithm. Time complexity is O(m * log (n)) where m is
86-
// the number of edges in the graph and n is number of nodes in it.
8723
func KruskalMST(n int, edges []Edge) ([]Edge, int) {
24+
// Initialize variables to store the minimum spanning tree and its total cost
25+
var mst []Edge
26+
var cost int
8827

89-
var mst []Edge // The resultant minimum spanning tree
90-
var cost int = 0
91-
92-
dsu := NewDSU(n)
28+
// Create a new UnionFind data structure with 'n' nodes
29+
u := NewUnionFind(n)
9330

31+
// Initialize each node in the UnionFind data structure
9432
for i := 0; i < n; i++ {
95-
dsu.MakeSet(Vertex(i))
33+
u.parent[i] = i
34+
u.size[i] = 1
9635
}
9736

37+
// Sort the edges in non-decreasing order based on their weights
9838
sort.SliceStable(edges, func(i, j int) bool {
9939
return edges[i].Weight < edges[j].Weight
10040
})
10141

42+
// Iterate through the sorted edges
10243
for _, edge := range edges {
103-
104-
if dsu.FindSetRepresentative(edge.Start) != dsu.FindSetRepresentative(edge.End) {
105-
44+
// Check if adding the current edge forms a cycle or not
45+
if u.Find(int(edge.Start)) != u.Find(int(edge.End)) {
46+
// Add the edge to the minimum spanning tree
10647
mst = append(mst, edge)
48+
// Add the weight of the edge to the total cost
10749
cost += edge.Weight
108-
dsu.UnionSets(edge.Start, edge.End)
50+
// Merge the sets containing the start and end vertices of the current edge
51+
u = u.Union(int(edge.Start), int(edge.End))
10952
}
11053
}
11154

55+
// Return the minimum spanning tree and its total cost
11256
return mst, cost
11357
}

‎graph/kruskal_test.go

+35-112
Original file line numberDiff line numberDiff line change
@@ -5,157 +5,80 @@ import (
55
"testing"
66
)
77

8-
func Test_KruskalMST(t *testing.T) {
9-
8+
func TestKruskalMST(t *testing.T) {
9+
// Define test cases with inputs, expected outputs, and sample graphs
1010
var testCases = []struct {
1111
n int
1212
graph []Edge
1313
cost int
1414
}{
15+
// Test Case 1
1516
{
1617
n: 5,
1718
graph: []Edge{
18-
{
19-
Start: 0,
20-
End: 1,
21-
Weight: 4,
22-
},
23-
{
24-
Start: 0,
25-
End: 2,
26-
Weight: 13,
27-
},
28-
{
29-
Start: 0,
30-
End: 3,
31-
Weight: 7,
32-
},
33-
{
34-
Start: 0,
35-
End: 4,
36-
Weight: 7,
37-
},
38-
{
39-
Start: 1,
40-
End: 2,
41-
Weight: 9,
42-
},
43-
{
44-
Start: 1,
45-
End: 3,
46-
Weight: 3,
47-
},
48-
{
49-
Start: 1,
50-
End: 4,
51-
Weight: 7,
52-
},
53-
{
54-
Start: 2,
55-
End: 3,
56-
Weight: 10,
57-
},
58-
{
59-
Start: 2,
60-
End: 4,
61-
Weight: 14,
62-
},
63-
{
64-
Start: 3,
65-
End: 4,
66-
Weight: 4,
67-
},
19+
{Start: 0, End: 1, Weight: 4},
20+
{Start: 0, End: 2, Weight: 13},
21+
{Start: 0, End: 3, Weight: 7},
22+
{Start: 0, End: 4, Weight: 7},
23+
{Start: 1, End: 2, Weight: 9},
24+
{Start: 1, End: 3, Weight: 3},
25+
{Start: 1, End: 4, Weight: 7},
26+
{Start: 2, End: 3, Weight: 10},
27+
{Start: 2, End: 4, Weight: 14},
28+
{Start: 3, End: 4, Weight: 4},
6829
},
6930
cost: 20,
7031
},
32+
// Test Case 2
7133
{
7234
n: 3,
7335
graph: []Edge{
74-
{
75-
Start: 0,
76-
End: 1,
77-
Weight: 12,
78-
},
79-
{
80-
Start: 0,
81-
End: 2,
82-
Weight: 18,
83-
},
84-
{
85-
Start: 1,
86-
End: 2,
87-
Weight: 6,
88-
},
36+
{Start: 0, End: 1, Weight: 12},
37+
{Start: 0, End: 2, Weight: 18},
38+
{Start: 1, End: 2, Weight: 6},
8939
},
9040
cost: 18,
9141
},
42+
// Test Case 3
9243
{
9344
n: 4,
9445
graph: []Edge{
95-
{
96-
Start: 0,
97-
End: 1,
98-
Weight: 2,
99-
},
100-
{
101-
Start: 0,
102-
End: 2,
103-
Weight: 1,
104-
},
105-
{
106-
Start: 0,
107-
End: 3,
108-
Weight: 2,
109-
},
110-
{
111-
Start: 1,
112-
End: 2,
113-
Weight: 1,
114-
},
115-
{
116-
Start: 1,
117-
End: 3,
118-
Weight: 2,
119-
},
120-
{
121-
Start: 2,
122-
End: 3,
123-
Weight: 3,
124-
},
46+
{Start: 0, End: 1, Weight: 2},
47+
{Start: 0, End: 2, Weight: 1},
48+
{Start: 0, End: 3, Weight: 2},
49+
{Start: 1, End: 2, Weight: 1},
50+
{Start: 1, End: 3, Weight: 2},
51+
{Start: 2, End: 3, Weight: 3},
12552
},
12653
cost: 4,
12754
},
55+
// Test Case 4
12856
{
12957
n: 2,
13058
graph: []Edge{
131-
{
132-
Start: 0,
133-
End: 1,
134-
Weight: 4000000,
135-
},
59+
{Start: 0, End: 1, Weight: 4000000},
13660
},
13761
cost: 4000000,
13862
},
63+
// Test Case 5
13964
{
14065
n: 1,
14166
graph: []Edge{
142-
{
143-
Start: 0,
144-
End: 0,
145-
Weight: 0,
146-
},
67+
{Start: 0, End: 0, Weight: 0},
14768
},
14869
cost: 0,
14970
},
15071
}
15172

152-
for i := range testCases {
153-
73+
// Iterate through the test cases and run the tests
74+
for i, testCase := range testCases {
15475
t.Run(fmt.Sprintf("Test Case %d", i), func(t *testing.T) {
76+
// Execute KruskalMST for the current test case
77+
_, computed := KruskalMST(testCase.n, testCase.graph)
15578

156-
_, computed := KruskalMST(testCases[i].n, testCases[i].graph)
157-
if computed != testCases[i].cost {
158-
t.Errorf("Test Case %d, Expected: %d, Computed: %d", i, testCases[i].cost, computed)
79+
// Compare the computed result with the expected result
80+
if computed != testCase.cost {
81+
t.Errorf("Test Case %d, Expected: %d, Computed: %d", i, testCase.cost, computed)
15982
}
16083
})
16184
}

‎graph/unionfind.go

+59
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
// Union Find Algorithm or Dynamic Connectivity algorithm, often implemented with the help
2+
//of the union find data structure,
3+
// is used to efficiently maintain connected components in a graph that undergoes dynamic changes,
4+
// such as edges being added or removed over time
5+
// Worst Case Time Complexity: The time complexity of find operation is nearly constant or
6+
//O(α(n)), where where α(n) is the inverse Ackermann function
7+
// practically, this is a very slowly growing function making the time complexity for find
8+
//operation nearly constant.
9+
// The time complexity of the union operation is also nearly constant or O(α(n))
10+
// Worst Case Space Complexity: O(n), where n is the number of nodes or element in the structure
11+
// Reference: https://www.scaler.com/topics/data-structures/disjoint-set/
12+
// Author: Mugdha Behere[https://github.com/MugdhaBehere]
13+
// see: unionfind.go, unionfind_test.go
14+
15+
package graph
16+
17+
// Defining the union-find data structure
18+
type UnionFind struct {
19+
parent []int
20+
size []int
21+
}
22+
23+
// Initialise a new union find data structure with s nodes
24+
func NewUnionFind(s int) UnionFind {
25+
parent := make([]int, s)
26+
size := make([]int, s)
27+
for k := 0; k < s; k++ {
28+
parent[k] = k
29+
size[k] = 1
30+
}
31+
return UnionFind{parent, size}
32+
}
33+
34+
// to find the root of the set to which the given element belongs, the Find function serves the purpose
35+
func (u UnionFind) Find(q int) int {
36+
for q != u.parent[q] {
37+
q = u.parent[q]
38+
}
39+
return q
40+
}
41+
42+
// to merge two sets to which the given elements belong, the Union function serves the purpose
43+
func (u UnionFind) Union(a, b int) UnionFind {
44+
rootP := u.Find(a)
45+
rootQ := u.Find(b)
46+
47+
if rootP == rootQ {
48+
return u
49+
}
50+
51+
if u.size[rootP] < u.size[rootQ] {
52+
u.parent[rootP] = rootQ
53+
u.size[rootQ] += u.size[rootP]
54+
} else {
55+
u.parent[rootQ] = rootP
56+
u.size[rootP] += u.size[rootQ]
57+
}
58+
return u
59+
}

0 commit comments

Comments
 (0)








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: http://github.com/TheAlgorithms/Go/commit/f2de2860f61ba7601ceb2b7fbbcc147b6d34cf7c

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy