图：从定义到遍历，我的一些实战心得

图这个数据结构，说实话，是很多初学者的一道坎。我记得自己刚学的时候，总觉得它比树复杂太多——树好歹有个明确的根节点，图呢？谁跟谁都能连，毫无章法。但后来在项目中做社交关系分析、地图导航时，我才真正体会到图的威力。今天我就带你把它彻底搞明白。

图的定义：到底什么是图？

图，说白了就是顶点和边的集合。用数学语言说：G = (V, E)。V 是顶点集，E 是边集。

举个例子：你微信里的好友关系，每个人是一个顶点，好友关系就是一条边。这就是一张典型的社交图。

图分两种：

  • 无向图：边没有方向。比如你和朋友的关系，你认识他，他也认识你。
  • 有向图：边有方向。比如微博的关注关系，你关注了他，他不一定关注你。

另外还有带权图，每条边带一个数值，比如地图上两个城市之间的距离。我在做物流路径规划时，就经常用带权图来建模。

核心概念速记：

  • 顶点的度：无向图中，一个顶点连接的边数
  • 入度/出度：有向图中，指向该顶点的边数 / 从该顶点出发的边数
  • 路径：从一个顶点到另一个顶点经过的顶点序列
  • 连通图：任意两个顶点之间都有路径

图的存储结构：邻接矩阵 vs 邻接表

存储图，业界就两种主流方式。我两种都用过，各有各的脾气。

邻接矩阵

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

// 邻接矩阵表示无向图
#define MAX_VERTEX 100
typedef struct {
    int vertices[MAX_VERTEX];       // 顶点数组
    int edges[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
    int vertexCount, edgeCount;
} GraphMatrix;

// 初始化
void initGraph(GraphMatrix *g, int n) {
    g->vertexCount = n;
    g->edgeCount = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g->edges[i][j] = 0;
}

// 添加边
void addEdge(GraphMatrix *g, int i, int j) {
    g->edges[i][j] = 1;
    g->edges[j][i] = 1; // 无向图对称
    g->edgeCount++;
}

优点：判断两个顶点是否相连，O(1) 搞定。我在做稠密图（边很多）时，首选邻接矩阵。

缺点：太费内存了。10000 个顶点，矩阵就是 1 亿个元素，直接爆炸。

我曾经踩过的坑：有一次用邻接矩阵存了 5000 个顶点的图，程序跑起来直接 OOM。后来换成邻接表，内存占用降了 90%。所以，稀疏图千万别用邻接矩阵。

邻接表

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

// 邻接表表示有向图
typedef struct EdgeNode {
    int adjVertex;          // 邻接顶点下标
    struct EdgeNode *next;  // 下一个边节点
} EdgeNode;

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

typedef struct {
    VertexNode vertices[MAX_VERTEX];
    int vertexCount, edgeCount;
} GraphList;

// 添加有向边 i -> j
void addDirectedEdge(GraphList *g, int i, int j) {
    EdgeNode *node = (EdgeNode*)malloc(sizeof(EdgeNode));
    node->adjVertex = j;
    node->next = g->vertices[i].firstEdge;
    g->vertices[i].firstEdge = node;
    g->edgeCount++;
}

优点：省内存，尤其适合稀疏图。遍历某个顶点的所有邻居也很方便。

缺点：判断两个顶点是否相连，需要遍历链表，O(度) 的时间。

我的个人习惯：如果图比较稠密（边数接近 n²），用邻接矩阵。如果图比较稀疏（边数远小于 n²），用邻接表。你想想看，这其实就是在时间和空间之间做权衡。

图的遍历：DFS 和 BFS

遍历图，说白了就是「怎么把图里的所有顶点都走一遍」。两种主流方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

DFS 的思路很简单：一条路走到黑，走不通了再回头。我习惯用递归来实现，代码非常简洁。

// DFS 递归实现（邻接矩阵版）
int visited[MAX_VERTEX] = {0};

void DFS(GraphMatrix *g, int v) {
    visited[v] = 1;
    printf("访问顶点: %d\n", v);
    
    for (int i = 0; i < g->vertexCount; i++) {
        if (g->edges[v][i] == 1 && !visited[i]) {
            DFS(g, i);
        }
    }
}

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

DFS 的时间复杂度：邻接矩阵是 O(n²)，邻接表是 O(n + e)。空间复杂度 O(n)，来自递归栈。

我在项目中用 DFS 做过拓扑排序和连通分量检测。比如检测一个社交网络里有多少个独立的圈子，DFS 一遍就能搞定。

广度优先搜索（BFS）

BFS 的思路是：一层一层往外扩。就像在水面上扔一颗石子，波纹一圈圈扩散。BFS 需要借助队列来实现。

// BFS 实现（邻接表版）
#include <queue>
using namespace std;

void BFS(GraphList *g, int start) {
    int visited[MAX_VERTEX] = {0};
    queue<int> q;
    
    visited[start] = 1;
    q.push(start);
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        printf("访问顶点: %d\n", v);
        
        EdgeNode *p = g->vertices[v].firstEdge;
        while (p) {
            if (!visited[p->adjVertex]) {
                visited[p->adjVertex] = 1;
                q.push(p->adjVertex);
            }
            p = p->next;
        }
    }
}

BFS 的时间复杂度跟 DFS 一样，邻接表是 O(n + e)，邻接矩阵是 O(n²)。空间复杂度 O(n)，来自队列。

DFS vs BFS 怎么选？

  • 想找最短路径？用 BFS。因为它是一层层扩散的，第一次到达目标顶点时，路径一定最短。
  • 想遍历整个图？两者都可以，但 DFS 的递归实现更简洁。
  • 想检测环？DFS 更方便，递归回溯时就能判断。
  • 我建议：如果图很深但很窄，用 DFS；如果图很宽但很浅，用 BFS。

知识体系总览

下面这张图，是我梳理的本章知识结构。你可以把它当作一张「地图」，学完后再回来看，会更有感觉。

图 (Graph) 图的定义 G = (V, E) 有向/无向/带权 存储结构 邻接矩阵 邻接表 图的遍历 DFS (栈/递归) BFS (队列) 应用：最短路径 · 拓扑排序 · 连通分量 时间复杂度：邻接矩阵 O(n²) | 邻接表 O(n+e) 空间复杂度：邻接矩阵 O(n²) | 邻接表 O(n+e)

避坑指南

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

  • 非连通图别忘了：DFS 和 BFS 的遍历函数里，一定要加一个循环，确保每个顶点都被访问到。我曾经漏掉这个，结果图里有一半顶点没遍历到，排查了半天。
  • 邻接表的内存释放：C 语言里，用 malloc 申请的边节点，记得在程序结束前 free 掉。不然内存泄漏会让你怀疑人生。
  • 有向图的度：邻接表存有向图时，出度好算，入度需要额外维护一个逆邻接表。我在做网页链接分析时，就因为这个吃了亏。
  • 递归深度：DFS 用递归实现虽然简洁，但如果图很深（比如几万个顶点连成一条线），递归栈会爆掉。这时候建议用显式的栈来模拟递归。

一个小技巧：调试图算法时，先用小规模数据（比如 5 个顶点）手动画出来，再对照代码跑一遍。我每次写新的图算法，都会先画图再编码，这样逻辑清晰，bug 也少。

图的内容就到这里。记住，图的精髓在于「顶点之间的关系」。无论是社交网络、地图导航还是依赖分析，本质上都是在处理关系。把这个想明白了，图就不再是难题。

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

← 上一章 📖 返回目录 下一章 →