将邻接矩阵转换为邻接列表表示的图形
data structurec++programming
邻接列表显示顶点的邻居。将邻接矩阵转置为列表可创建更紧凑、更高效的图形表示。从邻接矩阵切换到列表可改善内存使用、遍历周围节点和边缘信息。此转换支持广泛的图形处理操作和算法。
使用的方法
迭代方法
递归方法
迭代方法
迭代方法使用嵌套循环将邻接矩阵转换为列表。它将邻接列表边缘添加到每个矩阵元素。简单且非常适合小型到中型图形。 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);
// 打印邻接表
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);
// 打印邻接表
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
结论
处理和研究图形需要将图形的邻接矩阵转换为列表。矩阵到列表的转换可以改善存储、图形操作和邻居访问。在处理庞大的网络时，将邻接矩阵转换为邻接列表可以节省空间，并且仅保留有关顶点关系的最重要信息。邻接列表简化了邻居检测、度计算和图形探索。
