第二十六讲：图的基本概念——图的定义与术语、存储结构

各位同学，今天我们来聊聊图。说实话，图这个数据结构在嵌入式里用得不算特别频繁，但一旦用上，往往就是硬骨头——比如网络协议栈的路由表、自动驾驶的路径规划、甚至芯片内部互联的拓扑分析。我个人觉得，理解图的关键不在于背定义，而在于建立一种“关系思维”。

一、图的定义与核心术语

图，说白了就是一组顶点和一组边的集合。用数学语言说：G = (V, E)，V 是顶点集合，E 是边集合。但咱们搞工程的，更关心它怎么描述现实问题。

举个例子。我在做智能家居网关项目时，需要描述各个传感器节点之间的通信关系。每个传感器是一个顶点，它们之间的通信链路就是边。这时候，图就派上用场了。

1. 有向图 vs 无向图

• 无向图：边没有方向。比如邻居关系——你认识我，我也认识你。
• 有向图：边有方向。比如数据流向——传感器A向网关B发送数据，但B不一定向A发。

2. 顶点的度

无向图中，一个顶点连接的边数就是它的度。有向图里分入度和出度。我记得有一次调试一个环形缓冲区队列，发现数据总是卡在某个节点，一查是那个节点的入度远大于出度——说白了就是“收得多发得少”，堵住了。

3. 路径与连通性

• 路径：从一个顶点到另一个顶点经过的边序列。
• 连通图：任意两个顶点之间都有路径。如果图不连通，就分成多个连通分量。
• 强连通图（有向图）：任意两个顶点之间都有双向路径。

二、图的存储结构

图怎么存进计算机？两种主流方式：邻接矩阵和邻接表。选哪个？看场景。

1. 邻接矩阵

用一个二维数组存。arr[i][j] = 1 表示顶点 i 到 j 有边，0 表示没有。如果是带权图，就存权值。

// 邻接矩阵示例（无向图，5个顶点）
#define MAX_VERTEX 5
int graph[MAX_VERTEX][MAX_VERTEX] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 0},
    {0, 0, 1, 0, 0}
};

优点：判断两点之间是否有边，O(1) 搞定。适合稠密图（边多）。
缺点：浪费空间。1000个顶点就要 1,000,000 个元素，很多是0。

2. 邻接表

每个顶点维护一个链表，链表中存它所有邻居。说白了就是“谁跟我连着，我就记下谁”。

// 邻接表节点结构
typedef struct AdjNode {
    int vertex;           // 邻居顶点编号
    int weight;           // 权值（可选）
    struct AdjNode* next;
} AdjNode;

// 图结构
typedef struct Graph {
    int numVertices;
    AdjNode** adjLists;   // 指针数组，每个元素指向一个链表头
} Graph;

// 创建图
Graph* createGraph(int vertices) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->numVertices = vertices;
    g->adjLists = (AdjNode**)malloc(vertices * sizeof(AdjNode*));
    for (int i = 0; i < vertices; i++)
        g->adjLists[i] = NULL;
    return g;
}

// 添加边（无向图）
void addEdge(Graph* g, int src, int dest) {
    // 添加 src -> dest
    AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->vertex = dest;
    newNode->next = g->adjLists[src];
    g->adjLists[src] = newNode;
    
    // 添加 dest -> src（无向图需要双向）
    newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->vertex = src;
    newNode->next = g->adjLists[dest];
    g->adjLists[dest] = newNode;
}

优点：省空间。边少的时候特别划算。
缺点：判断两点是否相连，需要遍历链表，O(度) 的时间。

三、两种存储结构的对比

对比项	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V + E)
判断边是否存在	O(1)	O(度)
遍历所有边	O(V²)	O(V + E)
适合场景	稠密图、小规模图	稀疏图、大规模图
嵌入式适用性	RAM 够用时可考虑	更灵活，但注意内存管理

四、知识体系结构图

下面我用一张图来梳理本章的核心内容。你想想看，从图的定义出发，分出了术语和存储两大块，存储又分两种方式，各有优劣。

五、实际项目中的选择建议

嗯，这里要注意。很多初学者喜欢问“哪个更好”？其实没有绝对的好，只有适合不适合。

• 顶点少（比如 < 50）且边多：邻接矩阵。代码简单，查边快。
• 顶点多（比如 > 500）且边少：邻接表。省内存是王道。
• 嵌入式环境：我建议优先考虑邻接表，但要用静态数组模拟链表，避免动态内存分配带来的不确定性。

---