算法笔记 / A LEAF IN THE GARDEN

图基础

算法笔记 · 算法理论 / 图论。来自 Daily Learning 的学习笔记。

2026/05/104 分钟阅读更新于 2026/06/06

#算法 #算法理论 #图论

定义

由顶点集合 $V$ 和边集合 $E$ 组成的数据结构，记为 $G=(V,E)$ 。

$V \neq \emptyset$ ， $E \subseteq V \times V$ ， $|E| \leq |V|^2$ 。

基本术语

完全图

$G$ 中任意两顶点间都有边，称为完全图。

无向完全图： $n$ 个顶点， $|E|=n(n-1)/2$
有向完全图： $n$ 个顶点， $|E|=n(n-1)$

邻接

有边相连的顶点

A邻接到B： $A\rightarrow B$ 边存在
A邻接自B： $A\leftarrow B$ 边存在

度

与顶点邻接的边数。

入度：以该顶点为终点的边数。
出度：以该顶点为起点的边数。

无向图的总度数为 $2|E|$ 。有向图的总度数为 $|E|$ 。

路径

顶点序列 $v_1,v_2,\cdots,v_k$ ，其中 $v_i,v_{i+1}$ 之间有边，则称 $v_1,v_2,\cdots,v_k$ 为一条路径。

简单路径：不含重复顶点的路径。
回路：首尾顶点相同的路径。
简单回路：不含重复顶点的回路。
长度： $\sum_{i=1}^k w_i$ ， $w_i$ 为边 $(v_i,v_{i+1})$ 的权重。

子图

取原图的一部分顶点和边，构成满足图的定义的数据结构称为子图。

连通性

如果从任意一顶点出发，都可以到达图中其他任意顶点，则称该图是连通的。

连通分量：图中互相连通的极大子图。
强连通性：有向图的连通性。

$n$ 个顶点的连通图边数

无向图 $\geq n-1$

有向图 $\geq n$

生成树

连通无向图包含所有顶点的极小连通子图。

生成树边数 $= n-1$

图的存储

按点存储

邻接矩阵

$A_{nn}$ 表示 $n$ 个顶点的邻接矩阵

无权图

$A_{ij}=1$ 表示 $i$ 和 $j$ 之间有边，
$A_{ij}=0$ 表示 $i$ 和 $j$ 之间无边。

带权图

$A_{ij}$ 表示 $i$ 和 $j$ 之间边的权重。

要用特殊值标记无边的情况，如 $-1$ 或 $+\infty$

优点

容易判断是否有边
容易计算顶点的度

缺点

空间复杂度 $O(n^2)$ ，稀疏图浪费空间
统计边的数量效率低

代码

// 带权图
int A[MAXN][MAXN];
void init(int n){
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++) 
            // 无边设为无穷
            A[i][j] = INF;
        // 与自身权值0
        A[i][i] = 0;
    }
}
void add_edge(int u, int v, int w){
    A[u][v] = w;
    // 如果是无向图，还需要添加反向边
}

邻接表

链表数组，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。

链表里一般存储顶点的下标，方便快速访问。

优点

空间复杂度 $O(n+m)$ ，适合稀疏图
访问边的效率高

缺点

需要遍历链表，稠密图访问效率低
增加或删除边时，需要修改链表，效率低

代码

// 无权图
vector<list<int>> adj;
void init(int n){
    adj.resize(n);
}
void add_edge(int u, int v){
    adj[u].push_back(v);
    // 如果是无向图，还需要添加反向边
}

按边存储

边集数组

把所有边存成数组，每个元素包含边的起点、终点、权值。

优点

修改边容易
可以排序权值，用于Kruskal算法

缺点

访问效率低

代码

struct Edge {
    int from, to, w;
};
vector<Edge> edges;
void add_edge(int from, int to, int w) {
    edges.emplace_back(from, to, w);
}

链式前向星（推荐）

用三个数组（或结构体）

$head_u$ ：以 $u$ 为起点的第一条边编号
$next_i$ ：编号为 $i$ 的边的下一条边编号
$to_i$ ：编号为 $i$ 的边的终点
$w_i$ ：编号为 $i$ 的边的权重

还需要记录边的数量，添加边时用

代码

vector<int> head;
struct Edge {
    int nxt, to, w;
    Edge(int u, int v, int w): 
        nxt(head[u]), to(v), w(w){}
};
vector<Edge> edges;
int cnt;
void init(int n){
    head.resize(n, -1);
    // 如果是无向图，要开双倍空间
    cnt = 0;
}
void add_edge(int u, int v, int w) {
    cnt++;
    // 类似于头插法
    edges.emplace_back(u, v, w);
    head[u] = cnt;
}

图基础

定义

分类

按方向性

按密度

按权重