利用编程思维做题之将无向图的邻接矩阵转换为邻接表

在图的表示方法中，邻接矩阵和邻接表是两种常见的方式。邻接矩阵使用二维数组存储图中的连接关系，而邻接表使用链表存储每个节点的相邻节点。本文将设计一个算法，将无向图的邻接矩阵转换为对应的邻接表。

1. 理解问题

给定一个无向图的邻接矩阵，设计一个算法将其转换为邻接表。无向图的邻接矩阵是一个对称的二维数组，矩阵中的值表示两个节点之间是否有连接。我们需要基于邻接矩阵中的信息构建邻接表，其中每个节点都有一个链表存储其所有的相邻节点。

示例：

假设我们有如下的无向图邻接矩阵（4 个节点）：

0 1 2 3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]
转换后的邻接表表示如下：

0: 1 -> 2
1: 0 -> 3
2: 0 -> 3
3: 1 -> 2

关键点：

邻接矩阵：使用二维数组存储图中节点之间的连接关系。矩阵中值为 1 表示节点之间有边，值为 0 表示没有边。
邻接表：每个节点对应一个链表，链表中的元素表示与该节点直接相连的节点。

2. 输入输出

输入：

matrix：一个二维数组，表示无向图的邻接矩阵。

输出：

一个邻接表，使用链表表示每个节点的相邻节点。

3. 数据结构

邻接矩阵使用一个二维数组表示：

int matrix[MAX][MAX];
邻接表中的每个节点定义为一个结构体链表节点：

struct ListNode {
int vertex; // 相邻的节点
struct ListNode* next; // 指向下一个相邻节点
};
使用一个数组来存储邻接表，其中每个元素指向一个链表头节点，表示与该节点直接相连的所有节点。

struct ListNode* adjList[MAX];

4. 制定策略

为了将邻接矩阵转换为邻接表，我们可以按照以下步骤进行：

遍历矩阵：对于邻接矩阵中的每一个元素 matrix[i][j]，如果值为 1，则表示节点 i 和节点 j 之间有一条边。我们需要将节点 j 添加到节点 i 的邻接表中，并且由于无向图的对称性，也要将节点 i 添加到节点 j 的邻接表中。
创建邻接表：对于每个节点 i，我们动态分配链表节点，将每个相邻的节点（即 matrix[i][j] == 1 时）添加到链表中。

5. 实现代码

5.1 关键函数实现

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表节点
struct ListNode {
int vertex; // 相邻节点
struct ListNode* next; // 指向下一个相邻节点
};

// 创建一个新节点
struct ListNode* createNode(int v) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// 将邻接矩阵转换为邻接表
void convertMatrixToAdjList(int matrix[][MAX], int n, struct ListNode* adjList[]) {
for (int i = 0; i < n; i++) {
adjList[i] = NULL; // 初始化每个节点的邻接表为空

for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) { // 如果存在边
struct ListNode* newNode = createNode(j); // 创建一个新节点
newNode->next = adjList[i]; // 将新节点插入链表头部
adjList[i] = newNode; // 更新链表头节点
}
}
}
}

5.2 模拟过程

假设输入的邻接矩阵如下：

0 1 2 3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]

Step 1: 初始化邻接表

对于每个节点 i 初始化链表为 NULL。

Step 2: 遍历矩阵，生成邻接表

处理节点 0：
- 邻接矩阵 matrix[0][1] = 1，将节点 1 插入到节点 0 的邻接表中。
- 邻接矩阵 matrix[0][2] = 1，将节点 2 插入到节点 0 的邻接表中。
最终，节点 0 的邻接表为：0: 2 -> 1
处理节点 1：
- 邻接矩阵 matrix[1][0] = 1，将节点 0 插入到节点 1 的邻接表中。
- 邻接矩阵 matrix[1][3] = 1，将节点 3 插入到节点 1 的邻接表中。
最终，节点 1 的邻接表为：1: 3 -> 0
处理节点 2：
- 邻接矩阵 matrix[2][0] = 1，将节点 0 插入到节点 2 的邻接表中。
- 邻接矩阵 matrix[2][3] = 1，将节点 3 插入到节点 2 的邻接表中。
最终，节点 2 的邻接表为：2: 3 -> 0
处理节点 3：
- 邻接矩阵 matrix[3][1] = 1，将节点 1 插入到节点 3 的邻接表中。
- 邻接矩阵 matrix[3][2] = 1，将节点 2 插入到节点 3 的邻接表中。
最终，节点 3 的邻接表为：3: 2 -> 1

5.3 完整c代码

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表节点结构
struct ListNode {
int vertex; // 相邻节点的编号
struct ListNode* next; // 指向下一个相邻节点
};

// 创建一个新节点，表示某个相邻节点
struct ListNode* createNode(int v) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); // 分配内存给新节点
newNode->vertex = v; // 设置相邻节点编号
newNode->next = NULL; // 初始化 next 指针为 NULL
return newNode; // 返回新节点
}

// 将邻接矩阵转换为邻接表
void convertMatrixToAdjList(int matrix[][100], int n, struct ListNode* adjList[]) {
// 遍历邻接矩阵
for (int i = 0; i < n; i++) {
adjList[i] = NULL; // 初始化每个节点的邻接表为空

for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) { // 如果存在边，matrix[i][j] = 1
struct ListNode* newNode = createNode(j); // 创建一个新节点
newNode->next = adjList[i]; // 新节点的 next 指向当前邻接表的头节点
adjList[i] = newNode; // 更新邻接表的头节点为新节点
}
}
}
}

// 打印邻接表
void printAdjList(struct ListNode* adjList[], int n) {
for (int i = 0; i < n; i++) {
struct ListNode* temp = adjList[i]; // 获取当前节点的邻接表
printf("%d: ", i); // 打印节点编号

// 遍历并打印链表中的所有相邻节点
while (temp) {
printf("%d -> ", temp->vertex); // 打印相邻节点
temp = temp->next; // 移动到下一个相邻节点
}
printf("NULL\n"); // 链表结束
}
}

int main() {
int n; // 图中节点的数量
printf("请输入图中节点的数量: ");
scanf("%d", &n);

// 初始化邻接矩阵
int matrix[100][100];
printf("请输入邻接矩阵:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &matrix[i][j]); // 输入邻接矩阵
}
}

// 初始化邻接表
struct ListNode* adjList[100];

// 将邻接矩阵转换为邻接表
convertMatrixToAdjList(matrix, n, adjList);

// 打印邻接表
printf("\n邻接表表示:\n");
printAdjList(adjList, n);

return 0;
}

5.4 代码说明

convertMatrixToAdjList(int matrix[][100], int n, struct ListNode* adjList[])：将邻接矩阵转换为邻接表

参数：
- matrix：存储图的邻接矩阵，matrix[i][j] 表示节点 i 和节点 j 是否有边。
- n：节点的数量。
- adjList：邻接表数组，存储每个节点对应的链表。
通过遍历邻接矩阵，如果发现 matrix[i][j] == 1，表示节点 i 和节点 j 之间有边，此时将节点 j 添加到节点 i 的邻接表中。
由于是无向图，因此 matrix[i][j] == matrix[j][i]，我们只需处理一遍即可。