10_C 语言数据结构与算法：图结构 —— 复杂关系的网络建模

C 语言数据结构与算法：图结构 —— 复杂关系的网络建模

作为嵌入式零基础入门者或初级工程师，你是不是也常被这些问题困扰：要管理多个传感器节点的通信关系，不知道怎么组织数据才清晰；想规划设备间的最优通信路径，却找不到适配单片机资源的实现方法；面对多个模块的联动依赖，写出来的代码杂乱无章，后期调试维护全是坑？

其实这些“多对象、复杂关系”的问题，核心解决方案就是「图结构」。图结构是专门描述对象间关联关系的数据结构，小到传感器节点拓扑管理，大到工业设备联动网络，都能靠它理清逻辑、简化开发。今天这篇文章，就从零基础视角出发，用通俗的语言拆解图结构核心原理，讲清嵌入式场景下的两种实现方式和必备遍历算法，再结合实战案例给出可直接复用的C语言代码，帮你快速掌握用图结构搞定复杂关系建模的能力。

一、原理拆解：图结构的核心概念（通俗版）

在学具体实现前，我们先把图结构的核心概念掰扯明白。其实图结构一点都不复杂，就像一张“关系网”——比如社交软件里的好友关系、城市之间的交通网络，都能直接抽象成图。对于嵌入式开发来说，理解图结构，本质就是理解“设备/模块”和“它们之间的连接关系”。

1.1 图的基本组成：顶点和边

图的核心组成只有两个部分，不管多复杂的图，都离不开这两个元素，新手记准这两个就够了：

顶点（Vertex）：图中的“对象”，对应嵌入式场景里的传感器节点、设备模块、网关等。实操中建议用简单整数（比如0、1、2）标识每个顶点，这样后续写代码时处理起来更高效。

边（Edge）：顶点之间的“关系”，对应嵌入式场景里的“通信连接”“指令交互”等。边分两种，很好区分：

无向边：关系是双向的，比如传感器A和传感器B能互相发送数据，边没有方向；

有向边：关系是单向的，比如传感器只能向网关发送数据，网关不向传感器回传，边有明确的“从A指向B”的方向。

举个嵌入式场景的具体例子：一个由3个传感器节点（节点0、节点1、节点2）组成的采集网络，节点0能和节点1通信，节点1能和节点2通信，但节点0不能直接和节点2通信。把这个网络抽象成图就是：3个顶点（0、1、2）+ 两条无向边（0-1、1-2），逻辑瞬间就清晰了。

1.2 图的关键属性：权重和度

除了顶点和边，图还有两个核心属性，在嵌入式开发中经常用到，尤其是做路径规划时：

权重（Weight）：边的“附加信息”，比如传感器A到传感器B的通信延迟（单位ms）、设备间传输数据的误码率、城市间的距离等。做路径规划时，权重是核心参考——比如想选“通信延迟最小”的路径，就重点关注边的权重值。

度（Degree）：一个顶点连接的边的数量。比如传感器节点0只连了节点1，它的度就是1；节点1连了节点0和节点2，度就是2。如果是有向图，度还分“入度”（指向该顶点的边数，比如多少个传感器向网关发数据）和“出度”（从该顶点出发的边数，比如网关向多少个执行模块发指令）。

1.3 图的两种常见类型

根据边的特性，图主要分为两种，嵌入式场景中都会用到，新手要能区分：

无向图：边没有方向，顶点间关系是双向的。比如两个传感器互相通信、主控制器和显示屏的双向数据交互，都适合用无向图描述。

有向图：边有明确方向，顶点间关系是单向的。比如传感器向网关上传采集数据、主控模块向电机驱动模块下发转速指令，这些“单向交互”就适合用有向图描述。

另外，根据边的疏密程度，图还能分为“稠密图”和“稀疏图”，这两种图的实现方式不一样，后续会重点讲：① 稠密图：边很多，几乎每个顶点都和其他顶点相连（比如工业控制中的多模块全连接网络）；② 稀疏图：边很少，大部分顶点之间没有直接关系（比如传感器网络，每个节点只和附近几个节点通信）。

二、工程化分析：嵌入式场景下图的实现选型

在嵌入式开发中，图的实现主要有两种主流方式：邻接矩阵和邻接表。新手不用纠结“哪个更好”，关键看场景——核心选型依据是“图的疏密程度”和“单片机的资源限制”（比如内存大小、计算能力）。下面就详细讲两种方式的优劣和适用场景。

2.1 邻接矩阵（二维数组实现）

邻接矩阵是最直观的实现方式，核心是用一个“二维数组”来表示图——数组的行和列都对应图的顶点，数组元素就代表两个顶点之间是否有边、边的权重是多少。新手可以把它理解成“一张关系表”。

比如对于有n个顶点的图，我们定义一个n×n的二维数组graph[n][n]，规则很简单：

如果顶点i和顶点j之间有边，且权重为w，就设graph[i][j] = w；

如果顶点i和顶点j之间没有边，就设graph[i][j] = 0（或一个无穷大的数，比如0xFFFF，代表“不可达”）；

对于无向图，因为边是双向的，所以graph[i][j] = graph[j][i]；对于有向图，graph[i][j]和graph[j][i]可能不一样（比如i能指向j，但j不能指向i）。

优点：实现简单、逻辑直观，新手容易上手；判断两个顶点是否有边的速度特别快（时间复杂度O(1)），直接查数组元素就行；适合稠密图。

缺点：内存占用大，容易浪费。比如一个有100个顶点的图，需要100×100=10000个数组元素；如果是稀疏图，大部分元素都是0，相当于“占着内存不用”。而嵌入式单片机的内存通常很紧张（比如只有几KB），所以稀疏图不适合用邻接矩阵。

2.2 邻接表（数组+链表实现）

邻接表是嵌入式场景的主流实现方式，核心是用“数组+链表”的组合来表示图——用数组存储每个顶点，数组的每个元素对应一个链表，链表里只存储该顶点“实际连接”的顶点（以及边的权重）。简单说，就是“只存有用的关系，不浪费内存”。

比如对于有n个顶点的图，我们定义一个链表数组adj[n]，规则如下：

数组adj[i]对应的链表，只存储所有与顶点i直接相连的顶点（以及边的权重）；

对于无向图，顶点i连接顶点j时，要在adj[i]的链表中添加j，同时在adj[j]的链表中添加i（因为关系是双向的）；

对于有向图，顶点i指向顶点j时，只需要在adj[i]的链表中添加j即可（单向关系）。

优点：内存占用小，只存储实际存在的边，特别适合稀疏图。嵌入式场景中大部分图都是稀疏图（比如传感器网络，每个节点只和附近几个节点通信），所以邻接表是新手必须掌握的实现方式。

缺点：实现比邻接矩阵复杂一点（需要处理链表）；判断两个顶点是否有边时，需要遍历对应链表（时间复杂度O(k)，k是该顶点的度），比邻接矩阵慢。但对于嵌入式稀疏图场景，内存节省的优势远大于这个缺点。

2.3 嵌入式场景选型建议（新手直接照用）

场景类型	推荐实现方式	原因
稠密图（如工业控制中多个模块全连接）	邻接矩阵	实现简单，查询速度快；虽然内存占用大，但稠密图边多，闲置内存少，浪费不明显
稀疏图（如传感器网络、设备拓扑）	邻接表	内存占用小，适配单片机有限的内存资源；是嵌入式稀疏图场景的主流选择
顶点数量少（如≤20个）	邻接矩阵	顶点少，内存占用可控；实现简单，能快速完成开发，适合原型验证或简单场景
顶点数量多（如≥50个）	邻接表	内存占用优势明显；避免因顶点过多导致栈溢出或内存不足，适合复杂网络

三、C语言实现：邻接矩阵与邻接表实战

下面结合嵌入式实际场景，分别实现邻接矩阵（无向图，带权重）和邻接表（无向图，带权重），代码都附带详细注释，新手可以直接复制到Keil、IAR等开发环境中调试。我们以“5个传感器节点的通信网络”为案例：顶点0-4（对应5个传感器），边为0-1（权重2，代表通信延迟2ms）、0-2（权重3）、1-3（权重1）、2-3（权重4）、3-4（权重2）。

3.1 邻接矩阵实现（适合顶点少、简单场景）



#include "stdint.h"
#include "stdio.h"

// 宏定义：顶点数量（5个传感器节点）
#define VERTEX_NUM 5
// 宏定义：无穷大（表示两个顶点之间没有边）
#define INF 0xFFFF

// 邻接矩阵结构体（存储图的信息）
typedef struct {
    uint16_t vertex[VERTEX_NUM];          // 顶点数组（存储顶点标识，这里简化为0-4）
    uint16_t edge[VERTEX_NUM][VERTEX_NUM];// 边的权重矩阵
} Graph_AdjMatrix;

// 初始化邻接矩阵
// 参数：graph - 邻接矩阵指针
void graph_adjmatrix_init(Graph_AdjMatrix *graph) {
    if (graph == NULL) {
        return;
    }
    
    // 1. 初始化顶点（标识为0-4）
    for (uint8_t i = 0; i < VERTEX_NUM; i++) {
        graph->vertex[i] = i;
    }
    
    // 2. 初始化边的权重矩阵：默认所有顶点之间没有边（设为INF）
    for (uint8_t i = 0; i < VERTEX_NUM; i++) {
        for (uint8_t j = 0; j < VERTEX_NUM; j++) {
            graph->edge[i][j] = INF;
            // 顶点自身到自身的权重为0（无实际意义，规范处理）
            if (i == j) {
                graph->edge[i][j] = 0;
            }
        }
    }
    
    // 3. 添加边（无向图，双向权重相同）
    // 边0-1，权重2
    graph->edge[0][1] = 2;
    graph->edge[1][0] = 2;
    // 边0-2，权重3
    graph->edge[0][2] = 3;
    graph->edge[2][0] = 3;
    // 边1-3，权重1
    graph->edge[1][3] = 1;
    graph->edge[3][1] = 1;
    // 边2-3，权重4
    graph->edge[2][3] = 4;
    graph->edge[3][2] = 4;
    // 边3-4，权重2
    graph->edge[3][4] = 2;
    graph->edge[4][3] = 2;
}

// 打印邻接矩阵（调试用）
// 参数：graph - 邻接矩阵指针
void graph_adjmatrix_print(Graph_AdjMatrix *graph) {
    if (graph == NULL) {
        return;
    }
    
    printf("邻接矩阵（权重，INF表示无连接）：
");
    // 打印表头（顶点标识）
    printf("   ");
    for (uint8_t i = 0; i < VERTEX_NUM; i++) {
        printf("%4d", graph->vertex[i]);
    }
    printf("
");
    
    // 打印每行数据（行对应起始顶点，列对应目标顶点）
    for (uint8_t i = 0; i < VERTEX_NUM; i++) {
        printf("%4d", graph->vertex[i]);
        for (uint8_t j = 0; j < VERTEX_NUM; j++) {
            if (graph->edge[i][j] == INF) {
                printf("%4s", "INF");
            } else {
                printf("%4d", graph->edge[i][j]);
            }
        }
        printf("
");
    }
}

// 测试邻接矩阵实现
int main(void) {
    Graph_AdjMatrix graph;
    // 初始化邻接矩阵
    graph_adjmatrix_init(&graph);
    // 打印邻接矩阵，验证初始化结果
    graph_adjmatrix_print(&graph);
    
    return 0;
}

代码说明：邻接矩阵的核心就是“初始化二维数组+添加边”，逻辑特别简单，新手容易理解。打印后能直观看到每个顶点的连接关系和权重，方便调试。在嵌入式场景中，后续要判断顶点i和j是否连通、获取通信延迟，直接读graph->edge[i][j]就行——如果值不是INF，就是连通的，值就是权重。

3.2 邻接表实现（适合稀疏图，嵌入式主流）

邻接表的实现需要两步：先定义“链表节点”（存储相邻顶点和权重），再定义“链表数组”（存储每个顶点的相邻链表）。这里要重点注意：嵌入式场景尽量不用malloc动态分配内存（会产生内存碎片，导致程序不稳定），建议用静态数组存储链表节点，提前规划好最大数量。



#include "stdint.h"
#include "stdio.h"

// 宏定义：顶点数量（5个传感器节点）
#define VERTEX_NUM 5
// 宏定义：最大边数量（避免链表过长，根据实际场景调整）
#define MAX_EDGE_NUM 10

// 邻接表链表节点结构体（存储相邻顶点和边的权重）
typedef struct EdgeNode {
    uint16_t adj_vertex;                // 相邻顶点的标识
    uint16_t weight;                    // 边的权重
    struct EdgeNode *next;              // 指向下一个相邻节点的指针
} EdgeNode;

// 邻接表顶点结构体（存储每个顶点的信息和相邻链表头指针）
typedef struct VertexNode {
    uint16_t vertex;                    // 顶点标识
    EdgeNode *first_edge;               // 指向第一个相邻节点的指针
} VertexNode;

// 邻接表结构体（存储整个图的信息）
typedef struct {
    VertexNode adj_list[VERTEX_NUM];    // 顶点数组（每个元素对应一个顶点的链表）
    uint8_t vertex_num;                 // 实际顶点数量
    uint8_t edge_num;                   // 实际边数量
} Graph_AdjList;

// 静态链表节点数组（嵌入式场景：用静态内存代替malloc，避免内存碎片）
EdgeNode edge_nodes[MAX_EDGE_NUM];
// 静态内存索引（记录已使用的节点数量）
uint8_t edge_node_idx = 0;

// 申请一个静态链表节点（封装静态内存分配，避免动态分配）
// 返回值：空闲的链表节点指针，NULL表示无空闲节点
EdgeNode* get_edge_node(void) {
    if (edge_node_idx < MAX_EDGE_NUM) {
        // 初始化节点：next指针置空
        edge_nodes[edge_node_idx].next = NULL;
        return &edge_nodes[edge_node_idx++];
    }
    return NULL; // 无空闲节点
}

// 初始化邻接表
// 参数：graph - 邻接表指针
void graph_adjlist_init(Graph_AdjList *graph) {
    if (graph == NULL) {
        return;
    }
    
    // 1. 初始化顶点数量和边数量
    graph->vertex_num = VERTEX_NUM;
    graph->edge_num = 0;
    edge_node_idx = 0; // 重置静态内存索引
    
    // 2. 初始化每个顶点：顶点标识为0-4，相邻链表头指针置空
    for (uint8_t i = 0; i < graph->vertex_num; i++) {
        graph->adj_list[i].vertex = i;
        graph->adj_list[i].first_edge = NULL;
    }
}

// 向邻接表添加一条边（无向图，需要添加两条有向边）
// 参数：graph - 邻接表指针；v1/v2 - 两个顶点；weight - 边的权重
// 返回值：0-成功，1-失败（节点不足）
uint8_t graph_adjlist_add_edge(Graph_AdjList *graph, uint16_t v1, uint16_t v2, uint16_t weight) {
    if (graph == NULL || v1 >= graph->vertex_num || v2 >= graph->vertex_num) {
        return 1;
    }
    
    // 1. 添加边 v1->v2
    EdgeNode *node1 = get_edge_node();
    if (node1 == NULL) {
        return 1;
    }
    node1->adj_vertex = v2;
    node1->weight = weight;
    // 头插法：新节点插入到链表头部（插入效率高）
    node1->next = graph->adj_list[v1].first_edge;
    graph->adj_list[v1].first_edge = node1;
    
    // 2. 添加边 v2->v1（无向图，双向添加）
    EdgeNode *node2 = get_edge_node();
    if (node2 == NULL) {
        return 1;
    }
    node2->adj_vertex = v1;
    node2->weight = weight;
    node2->next = graph->adj_list[v2].first_edge;
    graph->adj_list[v2].first_edge = node2;
    
    // 3. 边数量加2（无向图一条边对应两个有向边）
    graph->edge_num += 2;
    return 0;
}

// 打印邻接表（调试用）
// 参数：graph - 邻接表指针
void graph_adjlist_print(Graph_AdjList *graph) {
    if (graph == NULL) {
        return;
    }
    
    printf("邻接表（顶点-相邻顶点：权重）：
");
    for (uint8_t i = 0; i < graph->vertex_num; i++) {
        printf("顶点%d：", graph->adj_list[i].vertex);
        EdgeNode *p = graph->adj_list[i].first_edge;
        // 遍历当前顶点的相邻链表
        while (p != NULL) {
            printf("%d(%d) ", p->adj_vertex, p->weight);
            p = p->next;
        }
        printf("
");
    }
}

// 测试邻接表实现
int main(void) {
    Graph_AdjList graph;
    // 1. 初始化邻接表
    graph_adjlist_init(&graph);
    
    // 2. 添加边（无向图）
    graph_adjlist_add_edge(&graph, 0, 1, 2);   // 边0-1，权重2
    graph_adjlist_add_edge(&graph, 0, 2, 3);   // 边0-2，权重3
    graph_adjlist_add_edge(&graph, 1, 3, 1);   // 边1-3，权重1
    graph_adjlist_add_edge(&graph, 2, 3, 4);   // 边2-3，权重4
    graph_adjlist_add_edge(&graph, 3, 4, 2);   // 边3-4，权重2
    
    // 3. 打印邻接表，验证结果
    graph_adjlist_print(&graph);
    
    return 0;
}

代码关键说明（新手必看）：

静态内存管理：用edge_nodes静态数组存储所有链表节点，用edge_node_idx记录已使用的节点数量，完全替代malloc，避免内存碎片，这是嵌入式开发的核心优化点；

头插法插入：新节点插入到链表头部，插入效率高（时间复杂度O(1)），不用遍历整个链表，适合嵌入式实时性要求；

无向图双向添加：因为是无向图，添加边时必须同时添加“v1→v2”和“v2→v1”，否则会出现“单向连通”的错误。

四、实战验证：图的遍历算法（DFS/BFS）与嵌入式应用

图的遍历是指“从一个起始顶点出发，访问图中所有能到达的顶点”，是图结构的核心应用基础。嵌入式场景中常用的两种遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）——DFS适合做“连通性检测”（比如判断两个传感器是否能通信），BFS适合做“最短路径查找”（比如找延迟最小的通信路径）。下面基于邻接表实现这两种算法，代码可直接复用。

4.1 深度优先搜索（DFS）：递归实现，简单直观

DFS的核心逻辑很形象：从起始顶点出发，“一条路走到黑”——先访问当前顶点的一个相邻顶点，再递归访问这个相邻顶点的相邻顶点，直到走不通了，再回溯到上一个顶点换另一条路。这种逻辑特别适合判断两个顶点是否连通，实现也简单（递归写法）。




// 全局变量：访问标记数组（记录顶点是否被访问过，0=未访问，1=已访问）
uint8_t visited[VERTEX_NUM] = {0};

// 深度优先搜索（DFS）递归实现
// 参数：graph - 邻接表指针；start_vertex - 起始顶点（从哪个顶点开始遍历）
void dfs_traverse(Graph_AdjList *graph, uint16_t start_vertex) {
    if (graph == NULL || start_vertex >= graph->vertex_num) {
        return; // 参数错误，直接返回
    }
    
    // 1. 访问当前顶点：这里打印顶点标识，实际场景可替换为业务逻辑（比如标记连通状态）
    printf("访问顶点：%d
", start_vertex);
    visited[start_vertex] = 1; // 标记为已访问，避免重复访问
    
    // 2. 遍历当前顶点的所有相邻顶点
    EdgeNode *p = graph->adj_list[start_vertex].first_edge;
    while (p != NULL) {
        // 3. 如果相邻顶点未被访问，递归访问它
        if (visited[p->adj_vertex] == 0) {
            dfs_traverse(graph, p->adj_vertex);
        }
        p = p->next; // 遍历下一个相邻顶点
    }
}

// 测试DFS遍历（在main函数中添加这3行代码即可）
memset(visited, 0, sizeof(visited)); // 重置访问标记数组（必须做，否则多次遍历会出错）
printf("深度优先搜索（DFS）从顶点0开始：
");
dfs_traverse(&graph, 0);

测试结果：从顶点0开始，DFS的访问顺序可能是“0→2→3→4→1”或“0→1→3→2→4”（具体取决于链表的插入顺序，两种都正常）。在嵌入式场景中，我们可以用这个算法做连通性检测——比如遍历后看visited[4]是否为1，如果是，说明顶点0和顶点4是连通的。

4.2 广度优先搜索（BFS）：队列实现，适合路径规划

BFS的核心逻辑是“一层一层访问”：从起始顶点出发，先访问它的所有相邻顶点（第一层），再依次访问每个相邻顶点的相邻顶点（第二层），直到所有可达顶点都访问完。BFS需要用“队列”存储待访问的顶点，适合查找“最短路径”（无权图或等权图场景，比如找跳数最少的通信路径）。




// 宏定义：队列最大长度（等于顶点数量即可，避免队列溢出）
#define QUEUE_MAX_LEN VERTEX_NUM

// 队列结构体（循环队列，存储待访问的顶点标识）
typedef struct {
    uint16_t data[QUEUE_MAX_LEN];
    uint8_t front; // 队头指针（取数据的位置）
    uint8_t rear;  // 队尾指针（存数据的位置）
} Queue;

// 初始化队列（清空队列）
void queue_init(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 入队（往队列里存数据）
// 参数：q - 队列指针；data - 要存的顶点标识
// 返回值：0-成功，1-队列满（存不下了）
uint8_t queue_enqueue(Queue *q, uint16_t data) {
    if ((q->rear + 1) % QUEUE_MAX_LEN == q->front) {
        return 1; // 队列满了，入队失败
    }
    q->data[q->rear] = data;
    q->rear = (q->rear + 1) % QUEUE_MAX_LEN; // 队尾指针后移（循环）
    return 0;
}

// 出队（从队列里取数据）
// 参数：q - 队列指针；data - 取出的顶点标识（输出参数）
// 返回值：0-成功，1-队列空（没数据了）
uint8_t queue_dequeue(Queue *q, uint16_t *data) {
    if (q->front == q->rear) {
        return 1; // 队列空了，出队失败
    }
    *data = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_MAX_LEN; // 队头指针后移（循环）
    return 0;
}

// 广度优先搜索（BFS）实现
// 参数：graph - 邻接表指针；start_vertex - 起始顶点
void bfs_traverse(Graph_AdjList *graph, uint16_t start_vertex) {
    if (graph == NULL || start_vertex >= graph->vertex_num) {
        return;
    }
    
    Queue q;
    queue_init(&q); // 初始化队列
    uint16_t current_vertex; // 当前访问的顶点
    EdgeNode *p; // 遍历相邻顶点的指针
    
    // 1. 重置访问标记数组（必须做，确保每次遍历独立）
    memset(visited, 0, sizeof(visited));
    
    // 2. 起始顶点入队，标记为已访问
    queue_enqueue(&q, start_vertex);
    visited[start_vertex] = 1;
    printf("广度优先搜索（BFS）从顶点0开始：
");
    
    // 3. 队列不为空时，循环出队访问
    while (queue_dequeue(&q, &current_vertex) == 0) {
        // 访问当前顶点
        printf("访问顶点：%d
", current_vertex);
        
        // 4. 把当前顶点的所有未访问相邻顶点入队
        p = graph->adj_list[current_vertex].first_edge;
        while (p != NULL) {
            if (visited[p->adj_vertex] == 0) {
                queue_enqueue(&q, p->adj_vertex);
                visited[p->adj_vertex] = 1; // 入队即标记，避免重复入队
            }
            p = p->next;
        }
    }
}

// 测试BFS遍历（在main函数中添加）
bfs_traverse(&graph, 0);

测试结果：从顶点0开始，BFS的访问顺序固定为“0→1→2→3→4”（先访问0的所有相邻顶点1、2，再访问1的相邻顶点3，最后访问3的相邻顶点4）。在嵌入式场景中，BFS是找最短路径的利器——比如这个案例中，从节点0到节点4的最短路径是“0→1→3→4”，权重和为2+1+2=5（延迟最小）。

4.3 嵌入式实战：传感器节点拓扑管理（直接复用代码）

把上面的邻接表和遍历算法组合起来，就能实现“传感器节点拓扑管理”的核心功能，新手可以直接复用这套逻辑：

拓扑构建：通过graph_adjlist_add_edge函数，把传感器节点间的通信关系、延迟（权重）添加到图中，形成完整的网络拓扑；

连通性检测：用DFS或BFS遍历，判断两个节点是否能通信（比如检测节点0和节点4是否连通，只需看遍历后visited[4]是否为1）；

最短路径查找：基于BFS（等权图，找跳数最少）或Dijkstra算法（带权图，找延迟最小），查找两个节点间的最优通信路径。

扩展示例：如果想检测节点0到节点4是否连通，且输出具体路径，可以在DFS/BFS函数中添加一个“路径数组”，记录每个顶点的前驱顶点（比如哪个顶点引导我们访问到当前顶点），遍历结束后回溯前驱顶点，就能得到完整路径。

五、问题解决：嵌入式图结构实现的避坑指南

新手在嵌入式场景实现图结构时，很容易踩一些“低级坑”，导致程序不稳定或功能异常。下面整理了5个高频坑和对应的避坑方法，新手一定要记牢：

5.1 坑1：使用动态内存分配（malloc）导致内存碎片

原因：单片机内存本就紧张，频繁用malloc分配、free释放内存，会产生“内存碎片”——小块内存闲置但无法被利用，后续再申请内存时会失败；

解决方法：用静态内存替代动态内存。比如邻接表的链表节点，用edge_nodes这样的静态数组存储，提前根据实际场景规划好最大节点数量（比如MAX_EDGE_NUM=10），完全不用malloc。

5.2 坑2：邻接表链表遍历陷入死循环

原因：无向图添加边时只加了单向（比如只加了v1→v2，没加v2→v1），导致遍历到某个顶点时出现死循环；或者申请链表节点时，next指针没置空，指向了随机地址；

解决方法：① 无向图添加边必须双向添加，严格执行“加v1→v2就必加v2→v1”；② 申请链表节点时，强制把next指针置空（比如get_edge_node函数中的edge_nodes[edge_node_idx].next = NULL）；③ 遍历链表时可以加个“最大次数限制”（比如最多遍历MAX_EDGE_NUM次），防止死循环。

5.3 坑3：遍历算法未重置访问标记数组

原因：多次调用DFS/BFS时，忘记重置visited访问标记数组，导致后续遍历只能访问到部分顶点，结果错误；

解决方法：每次调用DFS/BFS前，必须用memset(visited, 0, sizeof(visited))重置访问标记数组，确保每次遍历都是“从零开始”。

5.4 坑4：邻接矩阵内存占用过大导致栈溢出

原因：顶点数量较多时（比如50个），邻接矩阵的二维数组（50×50=2500个元素）如果定义在函数内部（栈上），会超出单片机的栈空间大小，导致栈溢出；

解决方法：① 顶点数量多（≥50）时，直接改用邻接表，从根源上减少内存占用；② 若必须用邻接矩阵，把二维数组定义为全局变量或静态变量（存储在数据段，不占用栈空间），比如static uint16_t edge[VERTEX_NUM][VERTEX_NUM];。

5.5 坑5：权重数据类型溢出

原因：计算路径总权重时，用了范围太小的数据类型（比如用uint8_t存储多个权重的和），当权重和超过数据类型最大值时，就会溢出，导致计算结果错误；

解决方法：根据实际场景选合适的数据类型。比如通信延迟通常是几ms到几十ms，多个权重和最多几百ms，用uint16_t就足够；如果是工业控制中的距离、时间等大数值，可用uint32_t。提前估算权重的最大可能和，避免溢出。

六、总结与互动引导

总结一下，图结构是嵌入式开发中处理“多对象复杂关系”的核心工具，新手掌握这几个核心要点就够了：① 图的基本组成是“顶点（设备/模块）”和“边（连接关系）”，关键属性是“权重（附加信息）”和“度（连接数量）”；② 嵌入式场景选型：稠密图/少顶点用邻接矩阵（简单），稀疏图/多顶点用邻接表（省内存，主流）；③ 遍历算法：DFS适合连通性检测，BFS适合最短路径查找；④ 核心优化：用静态内存替代动态内存，避免内存碎片。

对于嵌入式新手来说，不用一开始就追求复杂的图算法（比如Dijkstra、Floyd），先把邻接表的实现和DFS/BFS遍历搞懂、用熟，就能解决大部分实际场景的问题（比如传感器拓扑管理、设备连通性检测）。等基础扎实了，再逐步学习更复杂的路径规划算法。

如果这篇文章帮你打通了图结构在嵌入式中的应用思路，欢迎点赞、收藏、关注！如果在实际开发中遇到了具体问题（比如邻接表遍历死循环、内存溢出、路径规划实现不了），或者想了解Dijkstra算法的嵌入式实现，都可以在评论区留言讨论，我会一一回复～