设计一个算法将无向图的邻接矩阵转为对应邻接表的算法
时间: 2023-04-21 19:03:40 浏览: 708
算法步骤如下:
1. 创建一个空的邻接表,其中包含与无向图中顶点数相同的链表。
2. 遍历无向图的邻接矩阵,对于每个非零元素,将其对应的行和列所代表的顶点加入到邻接表中。
3. 对于每个顶点,将其邻接矩阵中对应的行或列中非零元素所代表的顶点加入到该顶点对应的链表中。
4. 返回生成的邻接表。
例如,对于以下无向图的邻接矩阵:
```
1 1
1 1 1
1 1 1
1 1
```
生成的邻接表如下:
```
-> 1 -> 2
1 -> -> 2 -> 3
2 -> -> 1 -> 3
3 -> 1 -> 2
```
其中,每个数字代表一个顶点,箭头表示该顶点所连接的其他顶点。
相关问题
设计将无向图的邻接矩阵转为对应邻接表的算法
1. 首先创建一个大小为n的空链表数组,n为无向图的顶点数。
2. 遍历邻接矩阵,对于每个顶点i,遍历其相邻的顶点j。
3. 如果邻接矩阵中i和j的值为1,则将j加入i的链表中,同时将i加入j的链表中。
4. 遍历完邻接矩阵后,得到的链表数组即为对应的邻接表。
c++设计算法将无向图邻接矩阵转换为邻接表,将邻接表转换为邻接矩阵
将无向图的邻接矩阵转换为邻接表,可以遍历整个矩阵,对于每个非零元素,将其所在的行和列分别对应到邻接表中的一个顶点,然后在这两个顶点的邻接表中分别添加对方作为相邻节点的边。具体实现代码如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> matrixToAdjList(vector<vector<int>> matrix) {
int n = matrix.size();
vector<vector<int>> adjList(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (matrix[i][j] != 0) {
adjList[i].push_back(j);
adjList[j].push_back(i);
}
}
}
return adjList;
}
```
将邻接表转换为邻接矩阵,可以先遍历邻接表中的所有顶点,对于每个顶点,遍历其邻接表中的节点,将其对应的邻接矩阵位置设为1。具体实现代码如下:
```c++
vector<vector<int>> adjListToMatrix(vector<vector<int>> adjList) {
int n = adjList.size();
vector<vector<int>> matrix(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j : adjList[i]) {
matrix[i][j] = 1;
matrix[j][i] = 1;
}
}
return matrix;
}
```
以上是将无向图的邻接矩阵转换为邻接表,以及将邻接表转换为邻接矩阵的具体实现代码,您可以根据实际情况进行调整。
阅读全文
相关推荐














