Running.Pig Running.Pig - 3 months ago 25
Python Question

Wrong output in Implementing Kruskal Algorithm in Python

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

at first glance, try this:

edges = list(graph['edges'])

instead

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