將鄰接矩陣轉換為圖的鄰接表表示

鄰接表顯示頂點的鄰居。將鄰接矩陣轉換為列表會建立更緊湊且更高效的圖形表示。從鄰接矩陣切換到列表可以提高記憶體使用率、遍歷到周圍節點以及邊緣資訊。這種轉換支援各種圖形處理操作和演算法。

使用的方法

  • 迭代方法

  • 遞迴方法

迭代方法

迭代方法使用巢狀迴圈將鄰接矩陣轉換為列表。它將鄰接列表邊新增到每個矩陣元素。簡單且適用於中小型圖。其時間複雜度為 O(V^2)。

演算法

  • 遍歷整個矩陣

  • 將所有元素新增到列表中

  • 返回包含所有列表的鄰接表

示例

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> convertMatrixToListIterative(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> adjList(n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                adjList[i].push_back(j);
            }
        }
    }

    return adjList;
}

int main() {
    vector<vector<int>> matrix = {{0, 1, 1},
                                  {1, 0, 1},
                                  {1, 1, 0}};

    vector<vector<int>> adjList = convertMatrixToListIterative(matrix);

    // Print the adjacency list
    for (int i = 0; i < adjList.size(); ++i) {
        cout << "Vertex " << i << ": ";
        for (int j = 0; j < adjList[i].size(); ++j) {
            cout << adjList[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

輸出

Vertex 0: 1 2 
Vertex 1: 0 2 
Vertex 2: 0 1

遞迴方法

遞迴函式將鄰接矩陣轉換為列表。從矩陣的第一行開始，它檢查每一列以查詢連線。它將頂點新增到邊的鄰接列表中。然後，該函式自身呼叫每個行，直到所有行都被處理。這種方法簡潔優雅，儘管遞迴深度可能會限制大型圖。

演算法

  • 編寫一個遞迴函式，並將矩陣及其行作為引數以及一個列表

  • 將所有元素新增到列表中

  • 返回包含所有列表的鄰接表

示例

#include <iostream>
#include <vector>

using namespace std;

void convertMatrixToListRecursive(vector<vector<int>>& matrix, vector<vector<int>>& adjList, int row) {
    int n = matrix.size();

    for (int j = 0; j < n; ++j) {
        if (matrix[row][j] == 1) {
            adjList[row].push_back(j);
        }
    }

    if (row < n - 1) {
        convertMatrixToListRecursive(matrix, adjList, row + 1);
    }
}

int main() {
    vector<vector<int>> matrix = {{0, 1, 1},
                                  {1, 0, 1},
                                  {1, 1, 0}};

    vector<vector<int>> adjList(matrix.size());

    convertMatrixToListRecursive(matrix, adjList, 0);

    // Print the adjacency list
    for (int i = 0; i < adjList.size(); ++i) {
        cout << "Vertex " << i << ": ";
        for (int j = 0; j < adjList[i].size(); ++j) {
            cout << adjList[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

輸出

Vertex 0: 1 2 
Vertex 1: 0 2 
Vertex 2: 0 1

結論

處理和研究圖需要將圖的鄰接矩陣轉換為列表。矩陣到列表的轉換提高了儲存、圖操作和鄰居訪問。在處理大型網路時，將鄰接矩陣轉換為鄰接列表可以節省空間並僅維護有關頂點關係的最重要資訊。鄰接表簡化了鄰居檢測、度計算和圖探索。

更新於：2023-07-14

1K+ 閱讀量

啟動您的 職業生涯

透過完成課程獲得認證

開始學習
廣告