Running.Pig - 11 months ago 133

Python Question

I am working on Krusal's Algorithm. However I failed to get the right output. I don't know where I made mistaks.

Here is my code:

`parent = dict()`

rank = dict()

def make_set(vertice):

parent[vertice] = vertice

rank[vertice] = 0

def find(vertice):

if parent[vertice] != vertice:

parent[vertice] = find(parent[vertice])

return parent[vertice]

def union(vertice1, vertice2):

root1 = find(vertice1)

root2 = find(vertice2)

if root1 != root2:

if rank[root1] > rank[root2]:

parent[root2] = root1

else:

parent[root1] = root2

if rank[root1] == rank[root2]: rank[root2] += 1

def kruskal(graph):

for vertice in graph['vertices']:

make_set(vertice)

minimum_spanning_tree = set()

edges = list(graph['edges'])

for edge in edges:

vertice1, vertice2, weight = edge

if find(vertice1) != find(vertice2):

union(vertice1, vertice2)

minimum_spanning_tree.add(edge)

return minimum_spanning_tree

graph = {

'vertices': [0,1, 2, 3, 4, 5],

'edges': set([ //(first node, second node, weight)

(0, 3,5),

(3, 5,2),

( 5, 4,10),

( 4, 1,3),

(1, 0,8),

(0, 2,1),(2,3,6),( 2,5,4),( 2,4,9),(2,1,7),

])

}

a = kruskal(graph)

print(a)

I found that if I change "Edges" into (weight, first node, second node) format, I can got right answer in format of (weight, first node, second node). But how can I modify it if I wanna use "Edges" in format of (first node, second node, weigth)?

Answer Source

at first glance, try this:

```
edges = list(graph['edges'])
```

instead

```
edges = sorted(graph['edges'], key=lambda e: e[3])
```