CODEWITHSUNDEEP
algorithmpseudocodekruskals-algorithm
Asia x3
Asia x3

Reputation: 616

Kruskal's Algorithm - Modify to matrix data structure?

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?

Kruskal Pseudo-code

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.

Upvotes: 0

Views: 2286

Answers (1)

chiwangc
chiwangc

Reputation: 3577

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.

Upvotes: 2

Related Questions