图¶

图（graph）是最通用的非线性数据结构，几乎所有现实世界的关系网络——社交关系、交通路网、任务依赖、调用图、电路网络——都可以抽象成一张图。形式化地，图是一个二元组 \(G = (V, E)\)，其中 \(V\) 是节点（vertex）集合，\(E\) 是边（edge）集合，每条边连接 \(V\) 中的两个节点。

基本分类¶

按边的方向性：

• 无向图（undirected）：边没有方向，\((u, v)\) 和 \((v, u)\) 等价。
• 有向图（directed）：边带方向，从 \(u\) 指向 \(v\) 的边和反向的边不一样。

按边的权重：

• 无权图：所有边等价。
• 带权图：每条边 \(e\) 上附加一个实数 \(w(e)\)，表示距离、代价、容量等。

按特殊性质：

• 简单图：没有自环，也没有重复边。
• 多重图：允许重复边。
• DAG（有向无环图）：有向图且没有环，是调度、依赖管理的基础模型。
• 树：无向连通且无环，是图的特殊情形。

图的存储¶

邻接矩阵¶

用一个 \(n \times n\) 的矩阵 \(A\) 存储图，其中 \(A_{ij}\) 表示边 \((i, j)\) 的信息（无权图存 0/1，带权图存权值，不存在时存 \(\infty\)）。

int A[N][N];
// 加边
A[u][v] = w;
A[v][u] = w;   // 无向图需要对称

优点是查询 \((u, v)\) 是否有边 \(O(1)\)；缺点是空间 \(O(n^2)\)，对稀疏图是巨大浪费。

邻接表¶

对每个节点 \(v\)，维护一个存放其所有邻居的链表或向量：

vector<vector<pair<int,int>>> adj(n);   // adj[u] 中每个元素是 {v, w}
adj[u].push_back({v, w});
adj[v].push_back({u, w});   // 无向图

邻接表的空间是 \(O(|V| + |E|)\)，稀疏图首选。遍历某个节点的邻居只需 \(O(\deg(v))\)，但查询 \((u, v)\) 是否相邻最坏要 \(O(\deg(u))\)。

链式前向星¶

工程和竞赛里常见的一种紧凑邻接表实现，用三个数组 head、next、to 存所有边，避免动态内存分配：

const int M = 200005;
int head[N], nxt[M], to[M], w[M], cnt = 0;

void add_edge(int u, int v, int ww) {
    to[cnt] = v;
    w[cnt]  = ww;
    nxt[cnt] = head[u];
    head[u] = cnt++;
}

// 遍历 u 的邻居
for (int e = head[u]; e != -1; e = nxt[e]) {
    int v = to[e], ww = w[e];
    // ...
}

遍历¶

图的两种最基本的遍历方式是深度优先（DFS）和广度优先（BFS）。对具体的算法细节（Dijkstra、Floyd、Tarjan 等）可以进一步参考 图算法，这里只展示最基本的遍历骨架。

DFS¶

vector<bool> visited(n, false);
void dfs(int u) {
    visited[u] = true;
    for (auto [v, w] : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}

DFS 天然用递归实现。递归层数过深时（比如链状图节点数上万），可能触发栈溢出，此时需要用显式栈改写。

BFS¶

queue<int> q;
vector<int> dist(n, -1);
q.push(src);
dist[src] = 0;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto [v, w] : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

BFS 在无权图上天然求出源点到所有点的最短路径。这一点是 BFS 最重要的性质——因为它按层扩展，先找到一个节点时走的一定是最短路。

一些基本概念¶

度：无向图中节点 \(v\) 的度 \(\deg(v)\) 是与其相连的边数。有向图中进一步区分入度 \(\deg^-(v)\) 和出度 \(\deg^+(v)\)。所有节点度之和 \(= 2|E|\)（每条边贡献 2）。

路径与环：节点序列 \(v_0, v_1, \dots, v_k\) 中相邻节点都有边相连则称为路径；起点等于终点的路径是环。简单路径要求中间节点不重复。

连通性：无向图中若任意两节点之间都存在路径，则称连通。有向图对应的概念分两种：强连通要求任意两点 \(u, v\) 都有 \(u \to v\) 和 \(v \to u\) 的路径；弱连通只要忽略方向后连通即可。

二分图：节点可以划分成两个不相交集合 \(A\) 和 \(B\)，使得每条边的两个端点分别属于 \(A\) 和 \(B\)。判断一张图是否二分图可以用染色法，本质是 BFS/DFS。

图的特殊表示¶

拓扑序¶

对 DAG 的所有节点排成线性序列，使得所有有向边 \((u, v)\) 都满足 \(u\) 在 \(v\) 的前面，这个序列就是拓扑序。拓扑序不唯一（除非图是链）。

Kahn 算法用 BFS 求拓扑序：

vector<int> indeg(n, 0);
for (int u = 0; u < n; ++u)
    for (auto [v, w] : adj[u]) ++indeg[v];

queue<int> q;
for (int u = 0; u < n; ++u)
    if (indeg[u] == 0) q.push(u);

vector<int> order;
while (!q.empty()) {
    int u = q.front(); q.pop();
    order.push_back(u);
    for (auto [v, w] : adj[u])
        if (--indeg[v] == 0) q.push(v);
}
if ((int)order.size() != n) {
    // 存在环，无拓扑序
}

反图¶

把有向图所有边方向翻转得到的图，称为反图。反图在解决「谁能到达 \(v\)」「强连通分量」等问题时经常用到。

稀疏图 vs 稠密图¶

边数接近最大可能（\(O(|V|^2)\)）的图称稠密图，否则称稀疏图。这两者的选择影响存储方式和算法实现：

现实世界的图绝大多数是稀疏图，因此邻接表和基于它的算法应用更广。