Kruskal algorithm

[hannonq]

Hi, I'm trying to run your Kruskal code with a big graph: 10000 nodes for a complete graph. I get a Segmentation Fault, which seems to come from a memory leak(?). I have 8GB of RAM and the program execution uses all of it, crashing the execution. Any ideas whether this is an implementation bug or is Python failing to free any allocated memory?

Thanks, Hannon.

[israelst]

Hi, I've never tried to run this code using an graph this big. Could you send it to me?

You may consider using a more efficient algorithms to special cases.

[hannonq]

That's how I generated the graph. I hope I didn't screw it up. The rest of the code is unchanged.

NUM_V = 10000
vertices = [x for x in range(NUM_V)]
edges = []
for i in range(NUM_V):
    for j in range(NUM_V):
        if i != j:
            edges.append((random.randint(10,300), i, j))

graph = {'vertices' : vertices, 'edges' : list(edges)}

minimum_spanning_tree = kruskal(graph)
print minimum_spanning_tree

I can't use other algorithms because my purpose is to do a statistical comparison between Kruskal's and Prim's algorithm.