将邻接矩阵转换为图的邻接表表示

邻接表显示顶点的邻居。将邻接矩阵转换为列表会创建更紧凑且更高效的图形表示。从邻接矩阵切换到列表可以提高内存使用率、遍历到周围节点以及边缘信息。这种转换支持各种图形处理操作和算法。

使用的方法

  • 迭代方法

  • 递归方法

迭代方法

迭代方法使用嵌套循环将邻接矩阵转换为列表。它将邻接列表边添加到每个矩阵元素。简单且适用于中小型图。其时间复杂度为 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+ 阅读量

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告