用c语言将一个无向图的邻接表转换成邻接矩阵
时间: 2023-10-06 21:07:01 浏览: 117
好的,我可以告诉你如何用C语言将一个无向图的邻接表转换成邻接矩阵。首先需要了解什么是邻接表和邻接矩阵。
邻接表是一种表示图的数据结构,它由一个数组和若干个链表组成,数组的每个元素对应一个链表,链表中存储与该节点相连的其他节点。邻接矩阵是由一个二维数组表示图的连接情况,其中元素a[i][j]表示节点i和节点j是否相连。
以下是一个示例代码,用C语言将一个无向图的邻接表转换成邻接矩阵:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 1000 //最大顶点数
// 邻接表结构体
typedef struct _EdgeNode {
int adjvex; // 相邻顶点序号
struct _EdgeNode *next;
} EdgeNode;
typedef struct _VNode {
EdgeNode *firstedge;
} VNode;
VNode List[MAX_VERTEX_NUM]; //图的邻接表
//输入无向图
void InputGraph(int &Vnum, int &Enum) {
scanf("%d %d", &Vnum, &Enum);
for (int i = 1; i <= Vnum; i++) {
List[i].firstedge = NULL;
}
int s, e;
EdgeNode *p1, *p2;
for (int i = 1; i <= Enum; i++) {
scanf("%d %d", &s, &e);
p1 = (EdgeNode*)malloc(sizeof(EdgeNode));
p1->adjvex = e;
p1->next = NULL;
if (List[s].firstedge == NULL) {
List[s].firstedge = p1;
} else {
p2 = List[s].firstedge;
while (p2->next != NULL) {
p2 = p2->next;
}
p2->next = p1;
}
p1 = (EdgeNode*)malloc(sizeof(EdgeNode));
p1->adjvex = s;
p1->next = NULL;
if (List[e].firstedge == NULL) {
List[e].firstedge = p1;
} else {
p2 = List[e].firstedge;
while (p2->next != NULL) {
p2 = p2->next;
}
p2->next = p1;
}
}
}
// 邻接表转邻接矩阵
void Convert(int Vnum, int Enum) {
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {0}; //邻接矩阵
EdgeNode *p;
for (int i = 1; i <= Vnum; i++) {
p = List[i].firstedge;
while (p != NULL) {
matrix[i][p->adjvex] = 1;
p = p->next;
}
}
// 打印邻接矩阵
for (int i = 1; i <= Vnum; i++) {
for (int j = 1; j <= Vnum; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int Vnum, Enum;
InputGraph(Vnum, Enum);
Convert(Vnum, Enum);
return 0;
}
```
希望能够帮助到你,如果还有其他问题,欢迎继续提问。
阅读全文