c语言将邻接矩阵转化为邻接表
时间: 2023-08-12 07:07:00 浏览: 47
好的,这是一个经典的图论问题。下面是 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100 // 设定图中最多有100个顶点
// 定义节点结构体
typedef struct Node {
int v; // 该节点对应的顶点编号
struct Node *next; // 指向下一个节点的指针
} Node;
// 定义邻接表结构体
typedef struct {
Node *head; // 指向第一个节点的指针
} AdjList[MAXN];
// 定义邻接矩阵结构体
typedef struct {
int matrix[MAXN][MAXN]; // 存储矩阵
int n; // 顶点个数
} Graph;
// 将邻接矩阵转化为邻接表
void matrix2list(Graph *g, AdjList adjList) {
int i, j;
Node *node;
// 遍历邻接矩阵
for (i = 0; i < g->n; i++) {
adjList[i].head = NULL; // 初始化每个链表的头指针为空
for (j = 0; j < g->n; j++) {
if (g->matrix[i][j] != 0) { // 如果顶点i和顶点j之间有边
// 创建一个新节点
node = (Node *)malloc(sizeof(Node));
node->v = j;
node->next = adjList[i].head;
// 将新节点插入到链表的头部
adjList[i].head = node;
}
}
}
}
int main() {
Graph g = {
{{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, // 邻接矩阵
3 // 顶点个数
};
AdjList adjList;
matrix2list(&g, adjList); // 转化为邻接表
// 输出邻接表
int i;
Node *p;
for (i = 0; i < g.n; i++) {
printf("%d: ", i);
p = adjList[i].head;
while (p != NULL) {
printf("%d ", p->v);
p = p->next;
}
printf("\n");
}
return 0;
}
```
代码的主要思路是:遍历邻接矩阵,如果顶点i和顶点j之间有边,则创建一个新节点,并将该节点插入到链表的头部。最终得到一个邻接表。