java - Kruskal 算法 - 按升序对邻接矩阵进行排序

Question

所以我在我的 kruskals 算法实现中使用了一个邻接矩阵，但我不确定我将如何对这个矩阵进行排序。

同时还记得加权边属于哪两个顶点。我正在考虑迭代矩阵并将权重最低的边添加到新矩阵并继续此过程，直到所有值都按升序排列并添加到新矩阵。

但是我最终不知道这些边值属于哪两个顶点。所以我想问问我如何才能按升序对我的值进行排序，同时记住每个值属于哪一行和哪一列。

有具体的方法吗？任何帮助都会很棒，谢谢。

Answer 1

您将无法按原样对矩阵进行排序 - 使用引用矩阵单元格的替代容器来存储边并对其进行排序。一个示例结构如下所示:

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;
  }
}