C语言无向图操作结构体选型与实现疑问

一、现有结构体成员解析 #

1. struct Edge *connections 的作用 #

这是每个节点的邻接链表头指针，用来挂接所有和当前节点相连的边。无向图中一条边连接两个节点，比如A和B相连，A的邻接链表会包含指向B的边，B的邻接链表也会包含指向A的边，这样遍历节点时就能找到所有相邻节点。

2. struct Node destination 的问题 #

这个设计存在严重缺陷：它直接存储完整的目标节点结构体，会造成数据冗余（同一个节点会被多次复制到不同边中），而且如果修改某个节点的信息（比如名称），所有边里的副本都要同步修改，极易出现数据不一致。正确的做法是存储目标节点的指针或者索引（比如节点在Graph数组中的下标）。

另外要注意：原struct Edge缺少struct Edge *next指针——没有这个指针，邻接链表无法链式存储多条边，只能存一条，这是必须补上的漏洞。

二、修正后结构体的核心函数实现 #

先修正结构体定义，再实现create_graph和add_edge：

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

#define MAX_CHAR 20

// 前向声明Node，让Edge可以引用Node指针
struct Node;

struct Edge {
    struct Node *destination;  // 改为指针，避免复制节点
    int days;
    struct Edge *next;         // 补上链表节点的next指针
};

struct Node {
    char name[MAX_CHAR];
    struct Edge *connections;
};

struct Graph {
    struct Node *nodes;
    int num_nodes;
};

1. 创建图（create_graph） #

初始化图的节点数组，完成基础内存分配：

struct Graph* create_graph(int num_nodes) {
    struct Graph *graph = malloc(sizeof(struct Graph));
    if (!graph) return NULL;

    graph->num_nodes = num_nodes;
    graph->nodes = malloc(num_nodes * sizeof(struct Node));
    if (!graph->nodes) {
        free(graph);
        return NULL;
    }

    // 初始化每个节点的邻接链表为空，名称置空
    for (int i = 0; i < num_nodes; i++) {
        strcpy(graph->nodes[i].name, "");
        graph->nodes[i].connections = NULL;
    }

    return graph;
}

2. 添加无向边（add_edge） #

无向图的边是双向的，需要给两个节点的邻接链表都添加对应边：

// 辅助函数：创建一条新边
struct Edge* create_edge(struct Node *dest, int days) {
    struct Edge *edge = malloc(sizeof(struct Edge));
    if (!edge) return NULL;
    edge->destination = dest;
    edge->days = days;
    edge->next = NULL;
    return edge;
}

int add_edge(struct Graph *graph, int src_idx, int dest_idx, int days) {
    // 参数合法性检查
    if (!graph || src_idx < 0 || src_idx >= graph->num_nodes || dest_idx < 0 || dest_idx >= graph->num_nodes) {
        return -1;
    }

    struct Node *src_node = &graph->nodes[src_idx];
    struct Node *dest_node = &graph->nodes[dest_idx];

    // 给源节点添加指向目标节点的边（头插法）
    struct Edge *new_edge = create_edge(dest_node, days);
    if (!new_edge) return -1;
    new_edge->next = src_node->connections;
    src_node->connections = new_edge;

    // 给目标节点添加指向源节点的边（无向图双向绑定）
    new_edge = create_edge(src_node, days);
    if (!new_edge) {
        // 回滚之前的操作，避免内存泄漏
        struct Edge *temp = src_node->connections;
        src_node->connections = src_node->connections->next;
        free(temp);
        return -1;
    }
    new_edge->next = dest_node->connections;
    dest_node->connections = new_edge;

    return 0;
}

三、更优的无向图实现方案 #

根据图的稀疏/稠密程度，推荐两种实用方案：

方案1：优化版邻接链表（适合稀疏图） #

就是上面修正后的实现，用节点指针存储目标，邻接链表管理边。

• 优点：节省空间，添加/删除边效率高
• 缺点：查找特定边需要遍历链表

方案2：邻接矩阵（适合稠密图） #

用二维数组直接存储边的权重，适合节点数量不多的场景：

#define MAX_NODES 100

struct GraphMatrix {
    char node_names[MAX_NODES][MAX_CHAR];
    int adj_matrix[MAX_NODES][MAX_NODES]; // 用-1表示无边，正数表示权重
    int num_nodes;
};

// 创建邻接矩阵图
struct GraphMatrix* create_graph_matrix(int num_nodes) {
    if (num_nodes > MAX_NODES) return NULL;
    struct GraphMatrix *graph = malloc(sizeof(struct GraphMatrix));
    if (!graph) return NULL;

    graph->num_nodes = num_nodes;
    // 初始化矩阵为无边状态
    for (int i = 0; i < num_nodes; i++) {
        strcpy(graph->node_names[i], "");
        for (int j = 0; j < num_nodes; j++) {
            graph->adj_matrix[i][j] = -1;
        }
    }
    return graph;
}

// 添加无向边（矩阵对称赋值）
void add_edge_matrix(struct GraphMatrix *graph, int src_idx, int dest_idx, int days) {
    if (!graph || src_idx < 0 || src_idx >= graph->num_nodes || dest_idx < 0 || dest_idx >= graph->num_nodes) {
        return;
    }
    graph->adj_matrix[src_idx][dest_idx] = days;
    graph->adj_matrix[dest_idx][src_idx] = days;
}

方案选择建议 #

• 稀疏图（节点多、边少）：选优化版邻接链表
• 稠密图（节点少、边多）：选邻接矩阵（查找边的时间复杂度为O(1)）
• 需要频繁按名称查找节点：可以额外维护哈希表，把节点名称映射到索引/指针

四、注意事项 #

• 内存管理：所有malloc分配的内存（图、边等）使用完后必须free，避免内存泄漏
• 去重：添加边前可以检查两个节点之间是否已存在边，避免重复添加

内容的提问来源于stack exchange，提问作者Diogo Ruas