C语言基于已存邻接链表数据构建图邻接矩阵的实现方法
基于已存储邻接链表生成邻接矩阵的实现方案
核心逻辑说明:
- 邻接矩阵是和节点数等维度的二维数组,位置
mat[i][j]值为1代表第i个节点和第j个节点存在连接,值为0代表无连接 - 你当前代码的节点索引规则:用户输入的节点编号为1n(n是总节点数),邻接链表数组`adj`是0n-1的数组下标,转换矩阵坐标时需要做1位的偏移,避免越界
现有代码存在的小问题提前修正,避免后续程序运行崩溃:
- malloc参数错误:原代码写的
malloc(sizeof(struct node*))仅申请了一个指针的内存大小,实际需要申请整个链表节点的存储空间,应改为malloc(sizeof(struct node)),否则内存分配不足会触发随机崩溃- 提示语逻辑错误:原代码输入提示为“输入边数”,但这个值实际是用来确定邻接链表数组长度的节点总数,应改成“Type in the number of nodes: ”,避免用户混淆
- 缺少输入校验:邻接关系输入时要校验值的范围,防止用户输入超范围的节点号导致数组越界
具体实现步骤
- 初始化邻接矩阵
动态申请n行n列的二维int数组,借助calloc自动将所有位置初始化为0(默认所有节点无连接),避免手动遍历赋值的冗余操作 - 遍历邻接链表填充矩阵值
逐一遍历邻接链表数组中每个节点的边链表,顺着链表拿到每个邻接节点的编号,转换为矩阵对应的下标,把矩阵对应位置的值设为1 - 实现邻接矩阵打印函数
按行列对齐的格式打印矩阵,加上节点编号做表头,方便和邻接链表的结果做对照;打印完成后及时释放申请的矩阵内存,避免内存泄漏
对应代码片段
在原程序的print_graf(adj,nodes);(打印邻接链表的语句)之后,加入以下逻辑:
// 1. 动态分配邻接矩阵,calloc自动初始化所有值为0 int *adj_mat[nodes]; for (int i = 0; i < nodes; i++) { adj_mat[i] = (int *)calloc(nodes, sizeof(int)); } // 2. 遍历邻接链表填充矩阵连接关系 for (int i = 0; i < nodes; i++) { struct node *cur = adj[i]; // 取当前节点的边链表头指针 while (cur != NULL) { int neighbor = cur->data; // 边界校验:邻接节点在合法范围内才写入矩阵 if (neighbor >= 1 && neighbor <= nodes) { // 输入的节点号是1开头,转0索引下标要减1 adj_mat[i][neighbor - 1] = 1; } cur = cur->next; } }
新增邻接矩阵的打印函数,放在原print_graf函数的下方即可:
void print_adj_matrix(int *mat[], int node_count) { printf("\n\n===== 邻接矩阵表示结果 =====\n"); // 打印列方向的节点表头 printf(" \t"); for (int col = 1; col <= node_count; col++) { printf("x%d\t", col); } printf("\n"); // 逐行打印矩阵内容 for (int row = 0; row < node_count; row++) { printf("x%d\t", row + 1); for (int col = 0; col < node_count; col++) { printf("%d\t", mat[row][col]); } printf("\n"); } // 释放矩阵动态申请的内存 for (int i = 0; i < node_count; i++) { free(mat[i]); } }
在main函数里填完邻接矩阵的值之后,直接调用打印函数即可:
// 接上面填完矩阵的代码 print_adj_matrix(adj_mat, nodes);
效果说明
如果是无向图,只要你在输入邻接关系时双向记录连接(比如节点1连节点2,会在节点1的链表里存2,节点2的链表里存1),生成的邻接矩阵天然是对称的,和实际图结构完全匹配,不需要额外做对称处理。
内容的提问来源于stack exchange,提问作者Vlad
相关产品推荐
相关产品推荐

