无向图的邻接矩阵和邻接表

邻接矩阵和邻接表是表示无向图的两种方式。邻接矩阵是一个二维数组，其中的行和列分别表示图中的节点，而数组中的元素表示这两个节点之间是否有边相连。如果有边相连，则该元素的值为1，否则为0。邻接表是一种链表的形式，表示图中每个节点的邻居节点。每个节点都有一个相关链表，链表中的节点表示该节点所连接的邻居节点。邻接表通常可以更有效地表示稀疏图。

相关问题

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。具体实现代码如下：

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

以上是将无向图的邻接矩阵转换为邻接表，以及将邻接表转换为邻接矩阵的具体实现代码，您可以根据实际情况进行调整。

实现将一个无向图邻接矩阵转换成邻接表

### 回答1：
将无向图的邻接矩阵转换成邻接表可以按照以下步骤进行：

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

其中，每个链表中的数字表示该顶点所连接的其他顶点的编号。

### 回答2：
邻接矩阵是一种表示图的方式，其中矩阵的每个元素表示两个顶点之间是否有边相连，即该矩阵为一个n*n的二维数组，其中n为图的结点数。而邻接表则是另一种表示图的方式，将每个结点与所有与之相连的结点及其边表示出来。

邻接表是由一个数组和若干个链表组成的数据结构。数组中每个元素表示一个结点，而该结点所对应的链表则记录了与该结点相连的所有结点及其边。

将邻接矩阵转换成邻接表的过程可以通过以下步骤实现：

1. 创建一个大小为n的数组，其中n为无向图的结点数。

2. 遍历邻接矩阵的每一个元素，对于值为1的元素（表示两个结点之间有边相连），将对应数组中的结点与相连结点添加到对应的链表中。

3. 遍历每个结点的链表，将链表中的所有边按照顺序输出即可。

需要注意的是，在邻接表中，每条边需要保存两个信息：起点和终点结点。

邻接表相对于邻接矩阵的优势在于可以减少存储空间的需求。当图的结点数量很大，但连接不是很繁密时，用邻接表存储图的信息可以显著地减少所需存储空间。而邻接矩阵则需一直维护一个n*n的矩阵，无论是否有相连的边存在。

因此，将无向图邻接矩阵转换成邻接表，可以在存储图的信息的同时，提升程序的运行效率，减少空间的浪费。

### 回答3：
无向图是指没有方向的图，邻接矩阵是一种图的表示方法，它可以将一个无向图表示为一个二维的矩阵。在邻接矩阵中，每行和每列分别代表每一个节点，若两个节点之间有边相连，则该位置的数值为1，否则为0。

将无向图的邻接矩阵转换为邻接表的过程，是将每一个节点以及与之相邻的节点之间的关系，表示成一张链表的形式。具体的步骤如下：

1. 创建一个大小为n（n为节点数量）的链表数组，数组中的每一个元素代表一个节点；
2. 对于邻接矩阵中第i行（或第i列）的元素，若其值为1，则在第i个节点的链表中添加一个指向第j个节点的指针；
3. 对于对称矩阵中的每一个元素，即邻接矩阵中的上三角或下三角区域，都需相应地在两个节点的链表中添加指向对方节点的指针。

以上三个步骤可以简单地用两个循环完成。代码如下：

//邻接矩阵转换为邻接表
vector<vector<int>> matrix_to_list(vector<vector<int>> matrix) {
    int n = matrix.size();
    vector<vector<int>> list(n, vector<int>()); //创建链表数组
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) { //对称矩阵只需操作一半
            if (matrix[i][j] == 1) {
                list[i].push_back(j); //在i的链表中添加j
                list[j].push_back(i); //在j的链表中添加i
            }
        }
    }
    return list;
}

以上代码中，使用了STL中的vector作为动态数组，依次遍历邻接矩阵的每个元素，在对应的两个节点的链表中添加指向对方节点的指针。最终返回的是一个链表数组，每一个元素都代表一个节点。这个节点的链表就是与之相邻的所有节点。

转换后的邻接表左右对称，占用空间相对邻接矩阵更小，并且可以更方便地进行节点相邻关系的访问和修改。因此，在处理无向图时，一般都会采用邻接表的方式来进行表示和计算。