You need to enable JavaScript to run this app. C语言基于已存邻接链表数据构建图邻接矩阵的实现方法
优惠活动
大模型
产品
解决方案
定价
更多

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: ”,避免用户混淆
  • 缺少输入校验:邻接关系输入时要校验值的范围,防止用户输入超范围的节点号导致数组越界

具体实现步骤

  1. 初始化邻接矩阵
    动态申请n行n列的二维int数组,借助calloc自动将所有位置初始化为0(默认所有节点无连接),避免手动遍历赋值的冗余操作
  2. 遍历邻接链表填充矩阵值
    逐一遍历邻接链表数组中每个节点的边链表,顺着链表拿到每个邻接节点的编号,转换为矩阵对应的下标,把矩阵对应位置的值设为1
  3. 实现邻接矩阵打印函数
    按行列对齐的格式打印矩阵,加上节点编号做表头,方便和邻接链表的结果做对照;打印完成后及时释放申请的矩阵内存,避免内存泄漏

对应代码片段

在原程序的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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.06 12:15:04