Kruskal's Algorithm - Modify to matrix data structure?

Question

This version of Kruskal's algorithm represents the edges with a adjacency list. How would I modify the pseudo-code to instead use a adjacency matrix?

I was thinking you we would need to use the weight of edges for instance (i,j), as long as its not zero. Assigning the vertices to i,j. I may be a bit confused on this pseudo-code of Kruskals.

There is nothing in the pseudocode specifying which data structures have to be used. But sorting the edges by weight will be hard in a matrix without an auxiliary representation. — Henry
– Henry, Commented Nov 22, 2016 at 5:18
For what it's worth, this pseudocode closely matches that seen on Wikipedia, which in the preamble specifies use of a disjoint-set data structure. — Daniel R. Collins
– Daniel R. Collins, Commented May 31, 2019 at 12:16

Community · Accepted Answer · 2017-05-23 11:59:57Z

2

As pointed out by Henry the pseudocode did not specify what concrete data structures to be used. It just appears that the adjacency list representation of graph is more convenient than the adjacency matrix representation in this case.

For adjacency matrix, you simply have to scan every entries of your matrix to sort the edges of graph G on line 4. And you are doing exactly the same thing when using the adjacency list representation.

In your case you may, for example, use a PriorityQueue to sort the edges by weight in non-decreasing order and discard entries with disconnected vertices. You can then iterate this data structure in the for-loop on line 5.

edited May 23, 2017 at 11:59

CommunityBot

11 silver badge

answered Nov 22, 2016 at 5:20

chiwangc

3,58716 gold badges28 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Kruskal's Algorithm - Modify to matrix data structure?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related