图论基础
分类: 图论
· 更新时间 2026-5-27 21:42:14
图论基础
图（Graph）由 顶点（Vertex） 和 边（Edge） 组成。
基本概念
| 概念 | 说明 |
|---|---|
| 顶点 | 图中的节点，通常编号为 |
| 边 | 连接两个顶点的连线，可能带有方向或权值 |
| 有向图 | 边有方向， 不同于 |
| 无向图 | 边无方向， 和 是同一条边 |
| 度 | 顶点的度 = 与该点相连的边数。有向图分为入度和出度 |
| 环（自环） | 起点 = 终点的边 |
| 重边 | 两点之间存在多条边 |
| 简单图 | 无自环、无重边的图 |
| 稀疏图 / 稠密图 | 为稀疏， 为稠密 |
| 路径 | 首尾相连的边的序列 |
| 简单路径 | 路径中每个顶点只出现一次 |
| 连通图 | 任意两点之间存在路径 |
| 树 | 无环连通图， 个点 条边 |
邻接矩阵
表示 到 的边权（无边则为 或 ）。
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;
}
邻接表（vector）
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});
}
链式前向星
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];