Kruskals算法 - 按照升序對一個鄰接矩陣進行排序

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