一、图的基本概念：图的存储与遍历

图这种数据结构，说实话，在嵌入式里用得不如链表、队列那么频繁。但一旦用上，往往都是硬骨头——比如路由协议、依赖分析、任务调度。我早年做的一个智能家居网关项目，就栽在图的遍历上，那次debug到凌晨三点，记忆犹新。

今天咱们就把图的基本功打扎实。先搞清楚图长什么样，再学会怎么存它，最后掌握两种最核心的遍历方式：DFS和BFS。

1.1 图是什么？

图由顶点和边组成。顶点就是节点，边就是节点之间的连线。

• 有向图：边有方向，A→B不等于B→A
• 无向图：边没方向，A-B等同于B-A
• 带权图：边上带数值，比如距离、成本

你想想看，城市之间的交通网络，就是个典型的带权无向图。顶点是城市，边是公路，权值是里程。

1.2 图的存储方式

存图，主流就两种：邻接矩阵和邻接表。选哪个？看场景。

1.2.1 邻接矩阵

用一个V×V的二维数组。matrix[i][j] = 1表示i到j有边，0表示没有。带权图就存权值。

// 邻接矩阵 —— 无向无权图
#define MAX_V 100
int graph[MAX_V][MAX_V] = {0};

void addEdge(int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;  // 无向图对称
}

优点：判断两点是否相连，O(1)搞定。
缺点：空间O(V²)。V=10000时，矩阵400MB，嵌入式扛不住。

1.2.2 邻接表

每个顶点维护一个链表，存它所有邻居。空间O(V+E)，稀疏图的福音。

// 邻接表 —— 无向无权图
#include <stdlib.h>

typedef struct AdjNode {
    int vertex;
    struct AdjNode* next;
} AdjNode;

typedef struct Graph {
    int V;
    AdjNode** array;  // 指针数组
} Graph;

Graph* createGraph(int V) {
    Graph* g = malloc(sizeof(Graph));
    g->V = V;
    g->array = malloc(V * sizeof(AdjNode*));
    for (int i = 0; i < V; i++)
        g->array[i] = NULL;
    return g;
}

void addEdge(Graph* g, int u, int v) {
    AdjNode* node = malloc(sizeof(AdjNode));
    node->vertex = v;
    node->next = g->array[u];
    g->array[u] = node;

    // 无向图再加一次
    node = malloc(sizeof(AdjNode));
    node->vertex = u;
    node->next = g->array[v];
    g->array[v] = node;
}

1.2.3 两种方式对比

对比项	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
查边(u,v)	O(1)	O(degree(u))
遍历所有边	O(V²)	O(V+E)
适合场景	稠密图、小图	稀疏图、大图

我个人习惯：嵌入式里90%的图都是稀疏图，所以邻接表用得更多。但如果你要频繁判断“两点是否相连”，矩阵更香。

1.3 深度优先搜索（DFS）

DFS的思路很简单：一条路走到黑，走不通就回头。说白了就是“不撞南墙不回头”。

实现方式有两种：递归和显式栈。递归代码短，但深度太大可能栈溢出。嵌入式里栈空间有限，我一般用显式栈。

// DFS —— 递归版
void DFS(int v, int visited[], Graph* g) {
    visited[v] = 1;
    printf("%d ", v);

    AdjNode* p = g->array[v];
    while (p) {
        if (!visited[p->vertex])
            DFS(p->vertex, visited, g);
        p = p->next;
    }
}

// 调用
int visited[MAX_V] = {0};
DFS(0, visited, g);

DFS的应用场景：

• 检测图中是否有环
• 拓扑排序
• 连通分量计数
• 迷宫寻路（一条路径）

1.4 广度优先搜索（BFS）

BFS是“层层推进”。先访问起点，再访问它所有邻居，然后是邻居的邻居……像水波一样扩散。

BFS必须用队列。我习惯用循环队列，避免动态内存分配。

// BFS —— 队列实现
#define MAX_Q 100
int queue[MAX_Q];
int front = 0, rear = 0;

void enqueue(int v) {
    queue[rear++] = v;
}

int dequeue() {
    return queue[front++];
}

int isEmpty() {
    return front == rear;
}

void BFS(int start, int visited[], Graph* g) {
    enqueue(start);
    visited[start] = 1;

    while (!isEmpty()) {
        int v = dequeue();
        printf("%d ", v);

        AdjNode* p = g->array[v];
        while (p) {
            if (!visited[p->vertex]) {
                visited[p->vertex] = 1;
                enqueue(p->vertex);
            }
            p = p->next;
        }
    }
}

BFS的应用场景：

• 无权图最短路径
• 社交网络“几度好友”
• 广播/泛洪算法
• 二分图检测

1.5 DFS vs BFS 怎么选？

场景	推荐	原因
找一条路径（任意）	DFS	内存占用小，找到即止
找最短路径（无权图）	BFS	天然保证最短
拓扑排序	DFS	后序遍历天然有序
连通分量	两者皆可	看习惯
图很大、深度很深	BFS	避免递归栈溢出

嗯，这里要注意：BFS虽然好，但队列可能很大。最坏情况下，BFS队列要存V个顶点。嵌入式里如果RAM吃紧，DFS可能更安全。

1.6 知识体系总览

下面这张图把本章的核心逻辑串起来了。我建议你保存下来，复习时一眼就能看到全貌。

1.7 小结

图这块，存储是基础，遍历是核心。邻接矩阵和邻接表各有利弊，选型时多想想你的顶点数和边数。DFS和BFS就像两把刀，DFS适合“深挖”，BFS适合“扩散”。

我在实际项目中，经常先用邻接表存图，然后根据需求选遍历方式。如果只是找连通性，DFS一把梭。如果要算最短路径，老老实实上BFS。

最后送你一句话：图算法不难，难的是选对工具。把今天这些基础打牢，后面讲最短路径、最小生成树时，你会觉得特别顺。

---

公众号:蓝海资料掘金营，微信deep3321