(self)
| 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 test coverage detected