第二十四章 图(一)：从概念到遍历，彻底搞懂图结构

图，终于讲到图了。说实话，在我早年做嵌入式开发时，图结构用得并不多。直到后来参与一个路由规划项目，才发现图简直是救星。你想想看，地图导航、社交网络、电路设计，哪个离得开图？今天我们就从最基础的概念讲起，一步步把图的存储和遍历吃透。

一、图的基本概念

图是什么？说白了，就是一堆顶点和连接它们的边。我习惯用这个比喻：顶点就像城市，边就像高速公路。但图比树自由多了——树有严格的父子关系，图可不管这套，谁跟谁都能连。

1. 图的定义

图 G 由两个集合组成：顶点集 V 和边集 E。记作 G = (V, E)。

• 顶点 (Vertex)：图中的基本元素，也叫节点。
• 边 (Edge)：顶点之间的连线，表示关系。

2. 图的分类

分类标准	类型	说明
边是否有方向	有向图 / 无向图	有向图的边像单行道，无向图像双行道
边是否有权重	带权图 / 无权图	带权图的边上有数值，比如距离、成本
是否有多条边	简单图 / 多重图	简单图不允许重复边，多重图允许

3. 常用术语

• 度 (Degree)：顶点关联的边数。有向图里分入度和出度。
• 路径 (Path)：从一个顶点到另一个顶点的顶点序列。
• 连通图 (Connected Graph)：任意两个顶点之间都有路径。
• 子图 (Subgraph)：从原图里挑一部分顶点和边组成的新图。

二、图的存储结构

图怎么存进计算机？我常用的就两种：邻接矩阵和邻接表。选哪个？看场景。稠密图用矩阵，稀疏图用邻接表。嗯，这是经验之谈。

1. 邻接矩阵

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

// 邻接矩阵实现 - 无向图
#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++;
}

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) {
    // 头插法：i->j
    EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjVertex = j;
    e->next = G->adjList[i].firstEdge;
    G->adjList[i].firstEdge = e;
    
    // 无向图还要加 j->i
    e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjVertex = i;
    e->next = G->adjList[j].firstEdge;
    G->adjList[j].firstEdge = e;
    
    G->edgeNum++;
}

3. 两种存储对比

对比项	邻接矩阵	邻接表
空间复杂度	O(n²)	O(n+e)
判断边是否存在	O(1)	O(度)
遍历所有边	O(n²)	O(n+e)
适用场景	稠密图	稀疏图

三、图的遍历

遍历图，说白了就是把所有顶点都走一遍。但图不像树有天然的层次，图里可能有环，你得小心别死循环。我常用的两种方法：DFS 和 BFS。

1. 深度优先搜索 (DFS)

DFS 的思路很简单：一条路走到黑，走不通了再回头。就像走迷宫，先选一个方向猛走，撞墙了再退回来换条路。

// DFS - 邻接矩阵实现
void DFS(MGraph *G, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);  // 访问顶点
    
    for (int i = 0; i < G->vertexNum; i++) {
        if (G->edge[v][i] == 1 && !visited[i]) {
            DFS(G, i, visited);
        }
    }
}

void DFSTraverse(MGraph *G) {
    int visited[MAX_VERTEX] = {0};
    for (int i = 0; i < G->vertexNum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
}

2. 广度优先搜索 (BFS)

BFS 像水波扩散，一圈一圈往外走。先访问离起点最近的，再访问次近的。用队列实现，先进先出。

// BFS - 邻接表实现
void BFS(ALGraph *G, int v, int visited[]) {
    int queue[MAX_VERTEX];
    int front = 0, rear = 0;
    
    visited[v] = 1;
    printf("%d ", v);
    queue[rear++] = v;
    
    while (front != rear) {
        int cur = queue[front++];
        EdgeNode *p = G->adjList[cur].firstEdge;
        
        while (p) {
            int neighbor = p->adjVertex;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                printf("%d ", neighbor);
                queue[rear++] = neighbor;
            }
            p = p->next;
        }
    }
}

void BFSTraverse(ALGraph *G) {
    int visited[MAX_VERTEX] = {0};
    for (int i = 0; i < G->vertexNum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
}

3. DFS vs BFS 对比

对比项	DFS	BFS
实现方式	递归/栈	队列
遍历顺序	纵向深入	横向扩展
空间复杂度	O(h)，h为深度	O(w)，w为最大宽度
适用场景	拓扑排序、连通分量	最短路径、层次遍历

四、知识体系总览

下面这张图，是我自己总结的本章知识框架。你看一遍，心里就有谱了。

图这块内容，说难不难，说简单也不简单。关键是把概念理清楚，把两种存储结构吃透，再把 DFS 和 BFS 的代码多写几遍。我个人建议：先拿邻接矩阵练手，因为直观；熟练了再转邻接表，因为实用。

---

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