一、图的基础概念：从零开始理解图

说实话，我刚学数据结构那会儿，觉得图是最有意思的部分。树是一种特殊的图，链表又是特殊的树——你想想看，整个数据结构体系其实都在围着图转。今天我就带你从最基础的概念开始，一步步把图这个东西吃透。

1.1 图的定义与术语

图用数学语言描述就是 G = (V, E)。V 是顶点集合，E 是边集合。举个例子：一个朋友圈，每个人是一个顶点，好友关系就是边。

几个关键术语，我当年面试时被问过无数次：

• 有向图 vs 无向图：边有没有方向。微博关注是有向的，微信好友是无向的。
• 完全图：任意两个顶点之间都有边。n 个顶点的无向完全图有 n(n-1)/2 条边。
• 度（Degree）：顶点关联的边数。有向图中还分入度和出度。
• 路径与回路：从一个顶点到另一个顶点的顶点序列。起点终点相同叫回路。
• 连通图与连通分量：任意两点都有路径叫连通图。非连通图由多个连通分量组成。

1.2 图的存储结构

图怎么存进计算机？两种主流方式：邻接矩阵和邻接表。各有各的脾气，选错了性能差十倍不止。

1.2.1 邻接矩阵

说白了就是一个二维数组。matrix[i][j] = 1 表示顶点 i 到 j 有边。无向图是对称矩阵。

// 邻接矩阵实现
#define MAX_VERTEX 100

typedef struct {
    int vertex[MAX_VERTEX];      // 顶点数组
    int edge[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
    int vertexNum, edgeNum;      // 顶点数和边数
} MGraph;

// 初始化图
void initGraph(MGraph *g, int n) {
    g->vertexNum = n;
    g->edgeNum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->edge[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(MGraph *g, int i, int j) {
    g->edge[i][j] = 1;
    g->edge[j][i] = 1;  // 无向图
    g->edgeNum++;
}

特性	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
判断两顶点是否相邻	O(1)	O(度)
遍历所有边	O(V²)	O(V+E)
适用场景	稠密图	稀疏图

1.2.2 邻接表

每个顶点维护一个链表，链表中存的是它相邻的顶点。空间省了，但查边慢了点。

// 邻接表实现
typedef struct EdgeNode {
    int adjVertex;              // 邻接顶点下标
    struct EdgeNode *next;      // 下一个邻接点
} EdgeNode;

typedef struct {
    int data;                   // 顶点信息
    EdgeNode *firstEdge;        // 第一条边
} VertexNode;

typedef struct {
    VertexNode adjList[MAX_VERTEX];
    int vertexNum, edgeNum;
} ALGraph;

// 添加边（无向图）
void addEdge(ALGraph *g, int i, int j) {
    EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjVertex = j;
    e->next = g->adjList[i].firstEdge;
    g->adjList[i].firstEdge = e;
    
    // 无向图需要加两次
    e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjVertex = i;
    e->next = g->adjList[j].firstEdge;
    g->adjList[j].firstEdge = e;
    
    g->edgeNum++;
}

1.3 图的遍历：DFS 与 BFS

遍历图就像走迷宫。两种走法：一条道走到黑（DFS），或者一层层往外扩（BFS）。

1.3.1 深度优先搜索（DFS）

核心思想：从起点出发，沿着一条路走到尽头，然后回溯。用递归或栈实现。

// DFS 递归实现
int visited[MAX_VERTEX];

void DFS(ALGraph *g, int v) {
    visited[v] = 1;
    printf("访问顶点: %d\n", v);
    
    EdgeNode *p = g->adjList[v].firstEdge;
    while (p) {
        if (!visited[p->adjVertex]) {
            DFS(g, p->adjVertex);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph *g) {
    for (int i = 0; i < g->vertexNum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < g->vertexNum; i++) {
        if (!visited[i]) {
            DFS(g, i);  // 处理非连通图
        }
    }
}

1.3.2 广度优先搜索（BFS）

一层层往外扩散，像水波一样。用队列实现，先访问的顶点先处理。

// BFS 实现
void BFS(ALGraph *g, int start) {
    int queue[MAX_VERTEX];
    int front = 0, rear = 0;
    
    for (int i = 0; i < g->vertexNum; i++) {
        visited[i] = 0;
    }
    
    visited[start] = 1;
    queue[rear++] = start;
    
    while (front != rear) {
        int v = queue[front++];
        printf("访问顶点: %d\n", v);
        
        EdgeNode *p = g->adjList[v].firstEdge;
        while (p) {
            if (!visited[p->adjVertex]) {
                visited[p->adjVertex] = 1;
                queue[rear++] = p->adjVertex;
            }
            p = p->next;
        }
    }
}

1.4 知识体系总览

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

1.5 避坑指南

最后分享几个我实际开发中遇到的坑，你遇到了能少走弯路：

• 内存泄漏：邻接表用 malloc 分配边节点，记得在程序退出时释放。我见过一个同事的代码跑了三天后内存耗尽，就是因为忘了 free。
• 非连通图：遍历时一定要检查所有顶点是否都被访问过。很多人只从起点开始遍历，结果漏掉了孤立的顶点。
• 递归深度：DFS 用递归实现时，如果图很深（比如 10000 个顶点），递归栈可能溢出。嵌入式环境栈空间有限，建议用显式栈代替递归。
• 有向图的度：有向图要分别统计入度和出度。我做过一个网页爬虫，就是因为没区分入度出度，导致链接分析全错了。