11-图论/01-图论基础

图论基础

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

基本概念

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

邻接矩阵

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

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];