| 2 | |
| 3 | |
| 4 | class Graph: |
| 5 | def __init__(self, vertices): |
| 6 | self.V = vertices |
| 7 | self.graph = [] |
| 8 | |
| 9 | def add_edge(self, u, v, w): |
| 10 | self.graph.append([u, v, w]) |
| 11 | |
| 12 | # Search function |
| 13 | |
| 14 | def find(self, parent, i): |
| 15 | if parent[i] == i: |
| 16 | return i |
| 17 | return self.find(parent, parent[i]) |
| 18 | |
| 19 | def apply_union(self, parent, rank, x, y): |
| 20 | xroot = self.find(parent, x) |
| 21 | yroot = self.find(parent, y) |
| 22 | if rank[xroot] < rank[yroot]: |
| 23 | parent[xroot] = yroot |
| 24 | elif rank[xroot] > rank[yroot]: |
| 25 | parent[yroot] = xroot |
| 26 | else: |
| 27 | parent[yroot] = xroot |
| 28 | rank[xroot] += 1 |
| 29 | |
| 30 | # Applying Kruskal algorithm |
| 31 | def kruskal_algo(self): |
| 32 | result = [] |
| 33 | i, e = 0, 0 |
| 34 | self.graph = sorted(self.graph, key=lambda item: item[2]) |
| 35 | parent = [] |
| 36 | rank = [] |
| 37 | for node in range(self.V): |
| 38 | parent.append(node) |
| 39 | rank.append(0) |
| 40 | while e < self.V - 1: |
| 41 | u, v, w = self.graph[i] |
| 42 | i = i + 1 |
| 43 | x = self.find(parent, u) |
| 44 | y = self.find(parent, v) |
| 45 | if x != y: |
| 46 | e = e + 1 |
| 47 | result.append([u, v, w]) |
| 48 | self.apply_union(parent, rank, x, y) |
| 49 | for u, v, weight in result: |
| 50 | print("%d - %d: %d" % (u, v, weight)) |
| 51 | |
| 52 | |
| 53 | g = Graph(6) |
no outgoing calls
no test coverage detected