深入浅出：C语言实现图数据结构的完全指南

2026-02-10 06:08:16 0条评论 2次阅读 0人点赞

作为一名开发者，我们经常需要处理复杂的关系网络，比如社交网络中的好友关系、地图导航中的路径规划，或者网络拓扑结构。在所有这些场景中，图都是最核心的数据结构。今天，我们将放下对高级语言的依赖，回到计算机科学的基石——C语言，来亲手实现这一强大的数据结构。

在C语言中实现图，不仅有助于我们理解指针和内存管理的精髓，还能让我们在性能敏感的底层开发中拥有更多的控制权。在这篇文章中，我们将从零开始，深入探讨如何在C语言中使用邻接矩阵和邻接表来表示图，并提供完整的、可直接运行的代码示例。我们将一起剖析每一行代码的作用，探讨其背后的算法逻辑，并分享一些实战中的性能优化技巧。

为什么选择 C 语言实现图？

虽然 Python 或 Java 提供了丰富的现成库，但 C 语言赋予了我们要掌控每一字节的权力。当我们需要处理海量数据或者对内存占用极其敏感的嵌入式系统时，C 语言实现的高效性是无可比拟的。我们将利用 C 语言强大的结构体和指针功能，构建出既灵活又高效的图结构。通过这种方式，我们可以完全掌控内存的分配与释放，避免垃圾回收机制带来的不确定性延迟，这在高频交易系统或实时操作系统（RTOS）中尤为重要。

图的核心概念：不仅仅是点和线

在我们开始写代码之前，让我们先明确一下我们要构建的对象到底是什么。图是由两个主要部分组成的数学结构：

  • 顶点： 图中的基本单元。你可以把它想象成地图上的“城市”，或者社交网络中的“用户”。顶点用于存储数据实体。
  • 边： 连接顶点的线条。它代表了两个顶点之间存在某种关系，比如“城市之间有道路”或“用户互为好友”。在 C 语言中，我们需要通过某种机制（如数组索引或指针）将这两个顶点关联起来。

#### 常见的图类型

在实现之前，你需要根据实际问题的性质选择图的类型：

  • 有向图： 边有明确的方向。就像 Twitter 的关注关系，A 关注 B，不代表 B 关注 A。在代码中，我们需要明确区分 INLINECODE701bc24b（源）和 INLINECODE9435d38b（目标）。
  • 无向图： 边是双向的。就像 Facebook 的好友关系，或者城市间的双向道路。在实现时，如果添加边 A->B，通常也需要添加 B->A。
  • 带权图： 每条边都有一个“权重”或“成本”。例如，导航地图中，权重可以是距离或通行时间。我们需要在存储边的数据结构中增加一个字段来保存这个数值。

方法一：邻接矩阵—— 简单直观但“昂贵”的选择

邻接矩阵是实现图最直接的方法。你可以把它想象成一个二维表格（二维数组），行和列分别代表图中的顶点。如果顶点 INLINECODE0c658925 和顶点 INLINECODE5cc15808 之间有边连接，我们在矩阵的 matrix[i][j] 位置填入 1（或权重值）；如果没有连接，则填入 0。

这种方法非常适合稠密图，即顶点之间有很多条边的情况。因为在稠密图中，矩阵中大部分位置都会被填满，空间利用率高。而且，查询两个顶点是否有边连接非常快，时间复杂度是 O(1)。

#### 代码实现：基于邻接矩阵的无向图

让我们来看看如何用 C 代码构建一个无向图的邻接矩阵。我们将定义一个 4x4 的矩阵（代表 4 个顶点），并演示如何添加边以及打印矩阵。

#include 

// 定义图中顶点的数量
#define V 4

// 初始化邻接矩阵，将所有元素设为 0（表示无边）
void initGraph(int mat[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            mat[i][j] = 0;
        }
    }
}

// 在图中添加边
// 因为是无向图，所以需要同时在 mat[i][j] 和 mat[j][i] 处置 1
void addEdge(int mat[V][V], int i, int j) {
    mat[i][j] = 1;
    mat[j][i] = 1;
}

// 辅助函数：打印邻接矩阵的内容
void displayMatrix(int mat[V][V]) {
    printf("
邻接矩阵表示：
");
    printf("   ");
    for(int k=0; k<V; k++) printf("%d ", k); // 打印列号
    printf("
");
    
    for (int i = 0; i < V; i++) {
        printf("%d: ", i); // 打印行号
        for (int j = 0; j < V; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("
");
    }
}

int main() {
    // 声明邻接矩阵
    int mat[V][V];

    // 初始化图
    initGraph(mat);

    // 添加边：连接 0-1, 0-2, 1-2, 2-3
    addEdge(mat, 0, 1);
    addEdge(mat, 0, 2);
    addEdge(mat, 1, 2);
    addEdge(mat, 2, 3);

    // 打印结果
    displayMatrix(mat);

    return 0;
}

输出结果：

邻接矩阵表示：
   0 1 2 3 
0: 0 1 1 0 
1: 1 0 1 0 
2: 1 1 0 1 
3: 0 0 1 0

#### 方法一的局限性

虽然邻接矩阵很简单，但你会注意到一个明显的缺点：空间浪费。

想象一下，如果你有一个包含 10,000 个顶点的图，但每个顶点只连接了 2 到 3 个其他顶点（稀疏图），你需要一个 INLINECODE3d7f600d 的整数数组。在大多数系统中，INLINECODEbaa11e7e 占用 4 字节，这意味着仅仅为了存储图结构，就消耗了近 400MB 的内存！而其中绝大部分存储的都是 0。这就是为什么我们在处理现实世界的大型稀疏数据时，通常会选择第二种方法。

方法二：邻接表 —— 内存优化的工业标准

在处理现实世界的问题（如社交网络分析、网页链接结构）时，图通常是稀疏的。这时，邻接表 是更优的选择。

邻接表的核心思想是：“只存储存在的关系”。我们创建一个数组，数组的每个索引对应一个顶点。数组中的每个元素又是一个链表的头指针，这个链表存储了所有与该顶点直接相连的其他顶点。

这种结构就像通讯录：你只记录你认识的人，而不是记录世界上所有你不认识的人（这在邻接矩阵中就是那些 0）。

#### 代码实现：基于链表的邻接表

在这个实现中，我们需要用到 C 语言的指针和结构体。我们将构建一个动态的系统，能够按需分配内存来存储边。

#include 
#include 

// 邻接表节点的结构体
struct AdjListNode {
    int dest;            // 目标顶点的索引
    struct AdjListNode* next; // 指向下一个邻接节点的指针
};

// 图的结构体，包含一个顶点数组（每个元素指向一个链表）
struct Graph {
    int V;               // 顶点的数量
    struct AdjListNode** array; // 邻接表数组
};

// 创建一个新的邻接表节点
// 辅助函数，用于在链表中插入新元素
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = 
        (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个包含 V 个顶点的图
struct Graph* createGraph(int V) {
    struct Graph* graph = 
        (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // 为每个顶点创建一个链表头指针数组
    graph->array = 
        (struct AdjListNode**) malloc(V * sizeof(struct AdjListNode*));

    // 初始化每个链表头为空
    for (int i = 0; i array[i] = NULL;

    return graph;
}

// 在无向图中添加一条边
void addEdge(struct Graph* graph, int src, int dest) {
    // 1. 添加从 src 到 dest 的边
    // 将新节点插入到 src 链表的头部
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src];
    graph->array[src] = newNode;

    // 2. 因为是无向图，所以也要添加从 dest 到 src 的边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest];
    graph->array[dest] = newNode;
}

// 打印图的结构
void printGraph(struct Graph* graph) {
    printf("
邻接表表示：
");
    for (int v = 0; v V; ++v) {
        struct AdjListNode* pCrawl = graph->array[v];
        printf("
 顶点 %d: ", v);
        while (pCrawl) {
            printf("-> %d ", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("
");
    }
}

int main() {
    // 创建一个包含 5 个顶点的图
    int V = 5;
    struct Graph* graph = createGraph(V);

    // 添加边构建图结构
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // 打印图
    printGraph(graph);

    return 0;
}

输出结果：

邻接表表示：

 顶点 0: -> 4 -> 1 

 顶点 1: -> 4 -> 3 -> 2 -> 0 

 顶点 2: -> 3 -> 1 

 顶点 3: -> 4 -> 2 -> 1 

 顶点 4: -> 3 -> 1 -> 0

#### 代码深度解析

让我们仔细看看 addEdge 函数。这是一个典型的链表插入操作，但我们做了一点优化。

你可能会问：“为什么我们要把新节点插入到链表的头部（头部插入），而不是尾部？”

答案是：性能。

  • 头部插入（当前做法）： 我们只需要修改新节点的 INLINECODEbc5791f1 指针指向当前的 INLINECODE37178e87，然后更新 head。这是 O(1) 的时间复杂度，无论链表有多长，速度都一样快。
  • 尾部插入： 我们必须遍历整个链表直到找到最后一个节点。这需要 O(N) 的时间，随着顶点连接数的增加，添加边的速度会越来越慢。

这就是实战中的一个重要细节：在构建静态图时，边的顺序通常不重要，所以我们优先选择头部插入以获得最佳性能。

进阶实战：带权图的邻接表实现

在实际应用中，比如我们要开发一个导航系统，仅仅是知道“两点相连”是不够的，我们还需要知道“距离”或“通行时间”。我们需要对结构体进行扩展，让它能够存储权重数据。

这展示了 C 语言结构体的灵活性：我们可以轻松地在节点中添加额外的字段，而不需要改变整个图的基础架构。

#include 
#include 

// 邻接表节点，增加了 weight 字段
struct AdjListNode {
    int dest;
    int weight; // 新增：权重
    struct AdjListNode* next;
};

struct Graph {
    int V;
    struct AdjListNode** array;
};

// 创建带权节点
struct AdjListNode* newAdjListNode(int dest, int weight) {
    struct AdjListNode* newNode = 
        (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight; // 初始化权重
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int V) {
    struct Graph* graph = 
        (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = 
        (struct AdjListNode**) malloc(V * sizeof(struct AdjListNode*));
    
    for (int i = 0; i array[i] = NULL;

    return graph;
}

// 添加带权边
void addEdge(struct Graph* graph, int src, int dest, int weight) {
    // 添加 src -> dest
    struct AdjListNode* newNode = newAdjListNode(dest, weight);
    newNode->next = graph->array[src];
    graph->array[src] = newNode;

    // 如果是无向图，同样添加 dest -> src，权重相同
    newNode = newAdjListNode(src, weight);
    newNode->next = graph->array[dest];
    graph->array[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    printf("
带权邻接表表示：
");
    for (int v = 0; v V; ++v) {
        struct AdjListNode* pCrawl = graph->array[v];
        printf("
 顶点 %d: ", v);
        while (pCrawl) {
            printf("-> %d (权:%d) ", pCrawl->dest, pCrawl->weight);
            pCrawl = pCrawl->next;
        }
        printf("
");
    }
}

int main() {
    int V = 4;
    struct Graph* graph = createGraph(V);

    // 添加边：(源, 目标, 权重)
    addEdge(graph, 0, 1, 10);
    addEdge(graph, 0, 2, 5);
    addEdge(graph, 1, 2, 15);
    addEdge(graph, 2, 3, 20);

    printGraph(graph);

    return 0;
}

常见陷阱与最佳实践

在使用 C 语言处理图时，作为开发者，你需要特别注意以下几点，这些都是在生产环境中容易踩的坑：

  • 内存泄漏： 这是 C 语言最大的敌人。在我们的代码中，INLINECODEec4f3759 用于分配节点内存，但如果不实现对应的 INLINECODEa173b98a 函数来释放内存，在长时间运行的服务器程序中，内存迟早会被耗尽。在实战开发中，务必编写一个遍历所有链表并逐个释放节点的清理函数。
  • 栈溢出： 如果你使用了递归算法（如深度优先搜索 DFS）来遍历一个包含数千个节点的图，非常容易导致栈溢出。在生产环境中，对于大型图，通常建议使用非递归（迭代）的方式，或者手动增加栈的大小限制。
  • 哈希冲突（如果优化）： 如果你追求极致性能，可能会考虑用哈希表代替链表来存储邻接节点，以实现 O(1) 的查询速度。但这时必须处理好哈希冲突，否则性能会急剧下降。对于大多数通用场景，简单的链表结构配合良好的 CPU 缓存命中率，往往表现非常出色。

总结与后续步骤

在这篇文章中，我们不仅掌握了图的基础概念，还通过 C 语言这一强大的工具，亲手实现了两种最核心的图表示法：邻接矩阵和邻接表。我们还进一步探讨了如何扩展这些结构以适应带权图的实际需求。

我们了解了邻接矩阵在处理稠密图时的便捷性，以及邻接表在处理稀疏图时的高效性。你现在手中的代码是构建更复杂算法（如最短路径、最小生成树）的坚实基础。

接下来的建议：

你可以尝试基于今天编写的代码，继续实现以下功能来巩固你的理解：

  • 实现 DFS 和 BFS： 尝试在上述代码基础上，编写深度优先搜索和广度优先搜索函数来遍历图。
  • 内存管理： 编写一个 destroyGraph 函数，确保程序退出前释放所有动态分配的内存。
  • 有向图改造： 修改 addEdge 函数，使其支持有向图（即只添加单向边），并观察打印结果的变化。

希望这篇指南能帮助你在 C 语言的图编程之路上走得更远。图的世界博大精深，掌握了底层的实现原理，你就掌握了性能的钥匙。编码愉快！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/41925.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年