CODEWITHSUNDEEP
javaalgorithmsortingmatrix
A Nayyer
A Nayyer

Reputation: 41

Kruskals Algorithm - Sort an adjacency matrix in ascending order

So I am using an adjacency matrix for my kruskals algorithm implementation, but I was unsure how I would go about sorting this matrix.

while still remembering which two vertices that weighted edge belongs to. I was thinking of iterating over the matrix and adding the lowest weight edge to a new matrix and continuing this process until all the values are in ascending order and added to that new matrix.

However I then end up not knowing which two vertices those edge values belonged to. So I wanted to ask how I would possibly go about ordering my values in ascending order, while remembering which row and column each value belongs to.

Is there a specific way of doing this? Any help would be great, thank you.

Upvotes: 1

Views: 643

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

You will not be able to sort the matrix as is - use an alternative container with reference to the matrix cell to store the edges and sort them. An example structure for this would look something like:

class Edge implements Comparable {
  int weight;
  int i; // x coordinate in the matrix
  int j; // y coordinate in the matrix
  int compareTo(Edge rhs) {
    return weight - rhs.weight;
  }
}

Upvotes: 1

Related Questions