图的存储

在 OI（信息学竞赛）中，图论是重要的内容，而要对图进行高效操作，必须掌握不同的图的存储方法。

📌 约定¶

图的点数记作 $n$，边数记作 $m$。
$d^+(u)$ 表示点 $u$ 的出度，即从 $u$ 出发的边的数量。
已默认读者已了解基本图论概念，如有疑问可先查阅《图论相关概念》。

一、直接存边¶

✅ 方法¶

使用结构体或多个数组存储边：每条边包含起点、终点和边权。

struct edge 
{
    int u, v, w; // 起点、终点、边权
} e[M]; // M 是边的上限

int main() 
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    return 0;
}

📊 复杂度¶

查询某条边是否存在：$O(m)$
遍历一个点的所有出边：$O(m)$
遍历整张图：$O(nm)$
空间复杂度：$O(m)$

🎯 应用¶

适用于 Kruskal 算法，需要对所有边排序。

二、邻接矩阵¶

✅ 方法¶

使用二维数组 adj[u][v] 表示 $u \to v$ 是否有边，或存储边权。

int adj[N][N];

int main() 
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
    {
        int u, v;
        cin >> u >> v;
        adj[u][v] = 1; // 无向图则同时设 adj[v][u] = 1;
    }

    // 若为带边权图：
    for (int i = 1; i <= m; i++) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u][v] = w; // 无向图设 adj[v][u] = w;
    }
    return 0;
}

遍历点 $u$ 的所有出边。

for (int v = 1; v <= n; v++)
{
    if (adj[u][v])
    {
        cout << v << " ";
    }
}

for (int v = 1; v <= n; v++)
{
    int w = adj[u][v];
    if (w)
    {
        cout << v << " " << w<< "\n";
    }
}

📊 复杂度¶

查询是否存在边：$O(1)$
遍历一个点的出边：$O(n)$
遍历整张图：$O(n^2)$
空间复杂度：$O(n^2)$

🎯 应用¶

适用于稠密图、点数少的场合。
支持快速查询是否存在边，但不支持重边。

三、邻接表¶

✅ 方法¶

使用 vector 动态数组存储每个点的出边。

vector<int> e[N]; // 不带权
vector<pair<int, int>> g[N]; // 带边权


int main() 
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) 
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v); // 无向图加 e[v].push_back(u)
    }

    // 带边权
    for (int i = 1; i <= m; i++) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        // 无向图加 g[v].push_back({u, w})
    }
    return 0;
}

遍历点 $u$ 的所有出边。

for (auto v : e[u])
{
    cout << v << " ";
}

for (auto it : g[u])
{
    int v = it.first;
    int w = it.second;
    cout << v << " " << w << "\n";
}

📊 复杂度¶

查询 $u \to v$ 是否存在：$O(d^+(u))$，排序后可用二分 $O(\log d^+(u))$
遍历点 $u$ 的出边：$O(d^+(u))$
遍历整张图：$O(n+m)$
空间复杂度：$O(m)$

🎯 应用¶

非常通用，适合大部分图的存储。
可方便地对出边排序，适合 Dijkstra、DFS、BFS 等。

四、链式前向星¶

✅ 方法¶

链式前向星是一种使用数组模拟链表实现的邻接表，支持快速存储和遍历边。其核心思想类似于 链表的头插法。

struct edge 
{
    int to, nxt, w;
} e[M];

int head[N], idx = 0; // head[u] 是点 u 的第一条出边的编号

void add(int u, int v, int w) 
{
    e[++idx] = {v, head[u], w}; // 新边插入到 u 的出边链表头部
    head[u] = idx;              // 更新 u 的第一条边为新插入的这条
}

int main() 
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);           // 有向图
        // add(v, u, w);        // 若为无向图，需要加一条反向边
    }
    return 0;
}

🔍 链表头插法讲解¶

以点 $u$ 的出边为一个链表，每次新加边 $u \to v$，就像在链表头部插入一个新节点：

e[++idx] = {v, head[u], w} 新建一条边，指向之前的第一条边。
head[u] = idx 更新链表头。

这样，点 $u$ 的所有出边就构成了一个链表，链表中的每一条边都通过 nxt 指向下一条边。

遍历方式如下：

for (int i = head[u]; i; i = e[i].nxt) 
{
    int v = e[i].to;
    int w = e[i].w;
    // 使用 v 和 w 做操作
}

📊 复杂度¶

查询是否存在某边：$O(d^+(u))$
遍历点 $u$ 出边：$O(d^+(u))$
遍历整张图：$O(n+m)$
空间复杂度：$O(m)$

🎯 应用¶

适用于各种图的高效存储，特别是在需要边编号的算法（如网络流）中。
如果边从 $i$ 和 $i^1$ 是互为反边（奇偶编号），可以高效处理反图。
不方便对边排序，无法直接快速判断某条边是否存在。

总结对比¶

存储方式	查询边是否存在	遍历出边效率	空间复杂度	支持边权	是否适用于稀疏图
直接存边	$O(m)$	$O(m)$	$O(m)$	✅	❌
邻接矩阵	$O(1)$	$O(n)$	$O(n^2)$	✅	❌
邻接表	$O(d^+(u))$	$O(d^+(u))$	$O(n+m)$	✅	✅
链式前向星	$O(d^+(u))$	$O(d^+(u))$	$O(n+m)$	✅	✅

建议：

稠密图：使用邻接矩阵。
稀疏图：使用邻接表或链式前向星。
边需要排序：使用邻接表。
需记录边编号 / 反边操作：链式前向星。