graphs/kruskal: add a test case to verify the correctness, fix styles… · coderjack/algorithms-in-python@c2a5033 · GitHub
Skip to content

Commit c2a5033

Browse files
meysam81cclausspoyeagithub-actions
authored
graphs/kruskal: add a test case to verify the correctness, fix styles (TheAlgorithms#2443)
* test/graphs/kruskal: adding a test case to verify the correctness of the algorithm Fixes TheAlgorithms#2128 * grahps/kruskal: running psf/black * graphs/kruskal: read edges in a friendlier fashion Co-authored-by: Christian Clauss <cclauss@me.com> * Update minimum_spanning_tree_kruskal.py * fixup! Format Python code with psf/black push * Update test_min_spanning_tree_kruskal.py * updating DIRECTORY.md Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: John Law <johnlaw.po@gmail.com> Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
1 parent 7d0d773 commit c2a5033

3 files changed

Lines changed: 55 additions & 16 deletions

File tree

‎DIRECTORY.md‎

Lines changed: 2 additions & 0 deletions

‎graphs/minimum_spanning_tree_kruskal.py‎

Lines changed: 17 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,5 @@
1-
if __name__ == "__main__":
2-
num_nodes, num_edges = list(map(int, input().strip().split()))
3-
4-
edges = []
5-
6-
for i in range(num_edges):
7-
node1, node2, cost = list(map(int, input().strip().split()))
8-
edges.append((i, node1, node2, cost))
9-
10-
edges = sorted(edges, key=lambda edge: edge[3])
1+
def kruskal(num_nodes, num_edges, edges):
2+
edges = sorted(edges, key=lambda edge: edge[2])
113

124
parent = list(range(num_nodes))
135

@@ -20,13 +12,22 @@ def find_parent(i):
2012
minimum_spanning_tree = []
2113

2214
for edge in edges:
23-
parent_a = find_parent(edge[1])
24-
parent_b = find_parent(edge[2])
15+
parent_a = find_parent(edge[0])
16+
parent_b = find_parent(edge[1])
2517
if parent_a != parent_b:
26-
minimum_spanning_tree_cost += edge[3]
18+
minimum_spanning_tree_cost += edge[2]
2719
minimum_spanning_tree.append(edge)
2820
parent[parent_a] = parent_b
2921

30-
print(minimum_spanning_tree_cost)
31-
for edge in minimum_spanning_tree:
32-
print(edge)
22+
return minimum_spanning_tree
23+
24+
25+
if __name__ == "__main__": # pragma: no cover
26+
num_nodes, num_edges = list(map(int, input().strip().split()))
27+
edges = []
28+
29+
for _ in range(num_edges):
30+
node1, node2, cost = [int(x) for x in input().strip().split()]
31+
edges.append((node1, node2, cost))
32+
33+
kruskal(num_nodes, num_edges, edges)

‎graphs/tests/test_min_spanning_tree_kruskal.py‎

Lines changed: 36 additions & 0 deletions

0 commit comments

Comments
 (0)