第1章：图的基础——从零开始认识图

大家好，我是老刘。今天咱们正式进入图的世界。

说实话，图这个数据结构，我当年学的时候也觉得挺抽象的。但后来在项目中做社交关系分析、地图导航，才发现图无处不在。你想想看，朋友圈的好友关系、地铁线路图、网页之间的链接，本质上都是图。

1.1 图的定义与基本术语

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

我习惯把顶点想象成"实体"，边想象成"关系"。比如在一个社交网络里，每个人是一个顶点，两个人是好友就是一条边。

基本术语一览

术语 含义 举个栗子
顶点 (Vertex) 图中的基本元素 社交网络中的用户
边 (Edge) 顶点之间的连线 用户之间的好友关系
有向图 边有方向 微博的关注关系（A关注B ≠ B关注A）
无向图 边没有方向 微信的好友关系（互为好友）
度 (Degree) 顶点关联的边数 你有100个微信好友，度就是100
路径 (Path) 从一个顶点到另一个顶点的顶点序列 从你家到公司经过哪些路口
连通图 任意两个顶点之间都有路径 一个完全连通的局域网

重点记忆：有向图中，顶点的度分为入度（指向该顶点的边数）和出度（从该顶点出发的边数）。这个在后面的拓扑排序里会反复用到。

1.2 图的存储结构

图怎么存到计算机里？这是个好问题。我做过一个项目，需要存储100万个用户的好友关系，选错存储方式直接内存爆炸。下面我把我用过的几种方式都讲一遍。

1.2.1 邻接矩阵

最简单粗暴的方式。用一个二维数组 matrix[n][n]，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;      // 顶点数和边数
} GraphMatrix;

// 初始化图
void initGraph(GraphMatrix *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(GraphMatrix *g, int i, int j) {
    g->edge[i][j] = 1;
    g->edge[j][i] = 1;  // 无向图对称
    g->edgeNum++;
}

我的经验：邻接矩阵适合稠密图（边很多的情况）。判断两个顶点是否相连，时间复杂度O(1)，非常快。但如果是稀疏图（比如社交网络，每个人平均只有几百个好友），用邻接矩阵就太浪费空间了——100万×100万的矩阵，你想想看有多大。

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;
} GraphAdjList;

// 添加边（无向图）
void addEdge(GraphAdjList *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++;
}

避坑指南：我曾经在项目中用邻接表存储有向图，结果忘记处理边的方向，导致图遍历时出现了"幽灵路径"。记住：有向图只添加一条边，无向图才添加两条。

1.2.3 十字链表（有向图专用）

这个稍微复杂一点，但处理有向图非常优雅。每个顶点维护两个链表：一个记录以它为起点的边（出边），一个记录以它为终点的边（入边）。

// 十字链表节点
typedef struct ArcNode {
    int tailVertex, headVertex;  // 弧尾和弧头
    struct ArcNode *hLink;       // 指向下一个弧头相同的节点
    struct ArcNode *tLink;       // 指向下一个弧尾相同的节点
} ArcNode;

typedef struct {
    int data;
    ArcNode *firstIn;   // 入边链表头
    ArcNode *firstOut;  // 出边链表头
} VertexNodeCross;

typedef struct {
    VertexNodeCross adjList[MAX_VERTEX];
    int vertexNum, edgeNum;
} GraphCross;

说实话，十字链表在面试中经常被问到，但实际项目中我用得不多。不过它确实能高效地同时获取一个顶点的入度和出度，这在某些场景下很有用。

1.2.4 邻接多重表（无向图专用）

邻接表存无向图有个问题：一条边被存了两次，删除操作很麻烦。邻接多重表解决了这个问题——每条边只存一次，但被两个顶点共享。

// 邻接多重表节点
typedef struct EdgeNodeMulti {
    int iVertex, jVertex;        // 边的两个顶点
    struct EdgeNodeMulti *iLink; // 指向顶点i的下一条边
    struct EdgeNodeMulti *jLink; // 指向顶点j的下一条边
} EdgeNodeMulti;

选型建议：

  • 稠密图（边接近n²）→ 邻接矩阵
  • 稀疏图（边远小于n²）→ 邻接表
  • 需要频繁查入度和出度 → 十字链表
  • 需要频繁删除边 → 邻接多重表

1.3 图的遍历：DFS与BFS

遍历图，说白了就是把所有顶点都走一遍。两种方式：深度优先（DFS）和广度优先（BFS）。

1.3.1 深度优先搜索（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->vertexNum; i++) {
        if (g->edge[v][i] == 1 && !visited[i]) {
            DFS(g, i);
        }
    }
}

void DFSTraverse(GraphMatrix *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);  // 处理非连通图
        }
    }
}

我的经验：DFS天然适合解决"是否存在路径"、"连通分量"这类问题。我在做迷宫寻路时，就是用DFS快速找到一条可行路径的。但要注意，DFS找到的不一定是最短路径。

1.3.2 广度优先搜索（BFS）

BFS是"层层推进"的思路。先访问离起点最近的顶点，再访问次近的，以此类推。需要借助队列实现。

// BFS遍历（邻接表版）
void BFS(GraphAdjList *g, int start) {
    int queue[MAX_VERTEX];
    int front = 0, rear = 0;
    int visited[MAX_VERTEX] = {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;
        }
    }
}

避坑指南：我曾经在BFS中忘记标记已访问顶点，结果队列里反复入队同一个顶点，直接死循环。记住：入队时就要标记visited，而不是出队时。否则可能重复入队。

1.3.3 DFS vs BFS 对比

对比项 DFS BFS
数据结构 栈（递归本质是栈） 队列
空间复杂度 O(h)，h为深度 O(w)，w为最大宽度
最短路径 不一定 一定能找到（无权图）
适用场景 连通性、拓扑排序、回溯 最短路径、层级遍历

知识体系总览

下面这张图是我自己整理的，把本章的核心知识点串起来了。你仔细看看，应该能对图有一个整体的认识。

图 (Graph) 基本定义 存储结构 遍历算法 应用场景 有向图/无向图 度/入度/出度 邻接矩阵 邻接表 DFS（深度优先） BFS（广度优先） 社交网络 地图导航 连通图 路径/回路 十字链表 邻接多重表 核心：顶点 + 边 → 存储 → 遍历 → 解决实际问题 选对存储结构，遍历效率翻倍

小结

这一章我们走完了图的"入门三件套"：定义、存储、遍历。我个人觉得，图最核心的就是选对存储结构和理解遍历思想。你只要把邻接表和DFS/BFS吃透，后面学最短路径、最小生成树就会轻松很多。

嗯，今天就到这里。代码我建议你亲手敲一遍，尤其是邻接表的实现，面试经常考。有什么问题，咱们下节课见。

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

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