图论基础

2026-05-16 8 min

WARNING
在未来将会被重写

图（Graph）

图是离散数学中描述关系结构的核心模型，记作：

G = (V, E)

其中， $V$ 表示节点（Vertex）集合， $E$ 表示边（Edge）集合。节点描述对象，边描述对象之间的关系，因此图本质上是在研究“对象 + 关系”的抽象结构。

节点（Vertex）

节点是图中的基本元素，通常表示一个实体。例如在社交网络中，一个用户可以被建模为一个节点。

若图包含 $n$ 个节点，则通常记为：

V = \{v_1, v_2, \dots, v_n\}

节点本身不重要，重要的是节点之间如何通过边连接。

边（Edge）

边用于描述两个节点之间的关系。若节点 $u$ 与节点 $v$ 相连，则可记作：

e = (u, v)

在无向图中， $(u,v)$ 与 $(v,u)$ 等价；而在有向图中二者不同，因为方向本身携带信息。

简单图（Simple Graph）

简单图是最基础的图结构，它满足：

不存在自环（Self-loop）
不存在重边（Multiple edges）

即任意两个节点之间最多只有一条边，并且节点不会与自己连接。

若简单无向图有 $n$ 个节点，则最多边数为：

\frac{n(n-1)}{2}

因为每两个不同节点之间最多只能连一条边。

带权图（Weighted Graph）

带权图在边上附加了“代价”或“距离”等数值，称为边权重（Weight）。

例如：

w(u,v)=5

表示从节点 $u$ 到节点 $v$ 的代价为 $5$ 。很多现实问题，例如最短路径、网络延迟、地图导航，本质上都需要使用带权图建模。

有向图与无向图

在无向图（Undirected Graph）中，边没有方向：

(u,v) = (v,u)

它表示一种“双向关系”。

而有向图（Directed Graph）中，边具有方向：

u \to v

此时 $(u,v)$ 与 $(v,u)$ 是不同的边。有向图更适合描述依赖、流动、控制等具有方向性的系统。

度（Degree）

节点的度表示与该节点关联的边数。

在无向图中，节点 $v$ 的度记为：

deg(v)

它等于与该节点连接的边数量。图中所有节点度数之和满足：

\sum_{v\in V} deg(v)=2|E|

因为每条边都会贡献两个端点。

入度与出度

在有向图中：

入度（In-degree）：指向该节点的边数
出度（Out-degree）：从该节点指出的边数

分别记作：

deg^-(v),\quad deg^+(v)

并满足：

\sum deg^-(v)=\sum deg^+(v)=|E|

因为每条有向边都会产生一个起点和一个终点。

稠密图与稀疏图

图的“稠密”与“稀疏”描述边数量相对于节点数量的关系。

若边数接近最大可能边数，则称为稠密图（Dense Graph）：

|E| \approx O(|V|^2)

若边数远小于节点平方规模，则称为稀疏图（Sparse Graph）：

|E| \approx O(|V|)

这个区分非常重要，因为不同类型图适合不同的数据结构与算法。

连通分量（Connected Component）

连通分量是图中“彼此可达”的最大节点集合。

也就是说，在同一个连通分量中，任意两个节点之间都存在路径：

u \rightsquigarrow v

而不同连通分量之间不存在路径连接。连通分量本质上反映了图被分裂成了多少个独立区域。

连通图（Connected Graph）

若一个无向图中任意两个节点都连通，则称该图为连通图。

形式化地说：

\forall u,v\in V,\quad \exists \text{ path}(u,v)

连通图意味着整个图是“一个整体”，不存在孤立区域。

树（Tree）

树是一类特殊的连通无环图（Connected Acyclic Graph）。

若树有 $n$ 个节点，则一定满足：

|E| = n-1

并且任意两个节点之间有且仅有一条简单路径。树的核心特点不是“长得像树”，而是它消除了冗余连接，因此具有最小连通结构。

森林（Forest）

森林是若干棵树组成的集合，本质上是“无环但不一定连通”的图。

若一个图不存在环，但包含多个连通分量，则每个连通分量都是一棵树，因此整体称为森林。

换句话说：

\text{Forest} = \text{Disjoint Union of Trees}

森林可以理解为“多个独立层级结构”的组合。

遍历图

DFS：对于每个节点，访问时标记这个点有没有被访问过。如果被访问过则跳过，若没有，则标记它，继续访问所有子节点

（因为有环的存在可能会回来）

对于遍历图的所有边也是同理，但这次是标记所有要访问的边。

遍历路径：找 src 到 dst 路径

约束：对于任何可行路径，节点只能出现一次
但是对于所有可行路径集合，节点可能出现多次。
因此队当前路径 path 进行标记，进入时标记，出来的时候需要解除标记。

实现

图通常通过 邻接表 或 邻接矩阵 实现。

下面是一个较为简单的基于邻接表的 C++ 实现：

class Graph {
public:
	struct Edge {
		int to; int weight;
		Edge(int t, int w) : to(t), weight(w) {}
	}
private:
	// 核心数据结构：邻接表
	// graph.size() == 图的节点数量
	// graph[u] 存储从节点 u 出发的所有边（出边）
	vector<vector<Edge>> graph;

public:
	Graph(int n) {
		// 初始化：节点数量
		graph = vector<vector<Edge>>(n);
	}

	// 向图添加带权重边
	void addEdge(int from, int to, int weight) {
		graph[from].emplace_back(to, weight);
	}

	// 删除一条有向边
	void removeEdge(int from, int to) {
		// 在 vector 中找到这个边，复杂度 O(out_degree(from))
		for (auto it = graph[from].begin(); it != graph[from].end(); it++) {
			if (it->to == to) {
				 graph[from].erase(it);
				 break;
			}
		}
	}

	// 检查两个节点是否相邻
	bool isNeighbor(int from, int to) {
		// 复杂度 O(V)
		for (const auto& e : graph[from]) {
			if (e.to == to) return true;
		}
		return false;
	};
}

Retypeset