查看“︁11-图论/01-图论基础”︁的源代码


== 图论基础 ==

图（Graph）由 '''顶点（Vertex）''' 和 '''边（Edge）''' 组成。

=== 基本概念 ===

{| class="wikitable"
! 概念 !! 说明
|-
| 顶点
| 图中的节点，通常编号为 <math>1 \sim n</math>
|-
| 边
| 连接两个顶点的连线，可能带有方向或权值
|-
| 有向图
| 边有方向，<math>u \to v</math> 不同于 <math>v \to u</math>
|-
| 无向图
| 边无方向，<math>(u, v)</math> 和 <math>(v, u)</math> 是同一条边
|-
| 度
| 顶点的度 = 与该点相连的边数。有向图分为入度和出度
|-
| 环（自环）
| 起点 = 终点的边
|-
| 重边
| 两点之间存在多条边
|-
| 简单图
| 无自环、无重边的图
|-
| 稀疏图 / 稠密图
| <math>m \approx n</math> 为稀疏，<math>m \approx n^2</math> 为稠密
|-
| 路径
| 首尾相连的边的序列
|-
| 简单路径
| 路径中每个顶点只出现一次
|-
| 连通图
| 任意两点之间存在路径
|-
| 树
| 无环连通图，<math>n</math> 个点 <math>n-1</math> 条边
|}

=== 邻接矩阵 ===

<math>g[u][v]</math> 表示 <math>u</math> 到 <math>v</math> 的边权（无边则为 <math>0</math> 或 <math>\infty</math>）。

<syntaxhighlight lang="cpp">
int g[1005][1005]; // 空间 O(n^2)，适合 n <= 5000 的稠密图

void add_edge(int u, int v, int w)
{
    g[u][v] = w;
    // 无向图：g[v][u] = w;
}
</syntaxhighlight>

=== 邻接表（vector） ===

<syntaxhighlight lang="cpp">
struct Edge
{
    int to, w;
};
vector<Edge> g[MAXN]; // 空间 O(m)

void add_edge(int u, int v, int w)
{
    g[u].push_back({v, w});
    // 无向图：g[v].push_back({u, w});
}
</syntaxhighlight>

=== 链式前向星 ===

<syntaxhighlight lang="cpp">
int head[MAXN], to[MAXM * 2], w[MAXM * 2], nxt[MAXM * 2], cnt;

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

// 遍历 u 的所有邻居
for (int i = head[u]; i; i = nxt[i])
    int v = to[i], weight = w[i];
</syntaxhighlight>

[[Category:图论]]
[[Category:三三文档]]