02.图的存储

在 OI 中，想要对图进行操作，就需要先学习图的存储方式。

约定

本文默认读者已阅读并了解了 图论相关概念 中的基础内容，如果在阅读中遇到困难，也可以在 图论相关概念 中进行查阅。

在本文中，用 $n$ 代指图的点数，用 $m$ 代指图的边数，用 $d^{+}(u)$ 代指点 $u$ 的出度，即以 $u$ 为出发点的边数。

直接存边

方法

使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）

参考代码

[list2tab]

• C++

  #include <iostream>
  #include <vector>
   
  using namespace std;
   
  struct Edge {
    int u, v;
  };
   
  int n, m;
  vector<Edge> e;
  vector<bool> vis;
   
  bool find_edge(int u, int v) {
    for (int i = 1; i <= m; ++i) {
      if (e[i].u == u && e[i].v == v) {
        return true;
      }
    }
    return false;
  }
   
  void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int i = 1; i <= m; ++i) {
      if (e[i].u == u) {
        dfs(e[i].v);
      }
    }
  }
   
  int main() {
    cin >> n >> m;
   
    vis.resize(n + 1, false);
    e.resize(m + 1);
   
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;
   
    return 0;
  }

• Python

  class Edge:
      def __init__(self, u=0, v=0):
          self.u = u
          self.v = v
   
   
  n, m = map(int, input().split())
   
  e = [Edge() for _ in range(m)]
  vis = [False] * n
   
  for i in range(m):
      e[i].u, e[i].v = map(int, input().split())
   
   
  def find_edge(u, v):
      for i in range(m):
          if e[i].u == u and e[i].v == v:
              return True
      return False
   
   
  def dfs(u):
      if vis[u]:
          return
      vis[u] = True
      for i in range(m):
          if e[i].u == u:
              dfs(e[i].v)

复杂度

查询是否存在某条边：$O(m)$。

遍历一个点的所有出边：$O(m)$。

遍历整张图：$O(nm)$。

空间复杂度：$O(m)$。

应用

由于直接存边的遍历效率低下，一般不用于遍历图。

在 Kruskal 算法 中，由于需要将边按边权排序，需要直接存边。

在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。

邻接矩阵

方法

使用一个二维数组 adj 来存边，其中 adj[u][v] 为 1 表示存在 $u$ 到 $v$ 的边，为 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储 $u$ 到 $v$ 的边的边权。

参考代码

[list2tab]

• C++

  #include <iostream>
  #include <vector>
   
  using namespace std;
   
  int n, m;
  vector<bool> vis;
  vector<vector<bool>> adj;
   
  bool find_edge(int u, int v) { return adj[u][v]; }
   
  void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int v = 1; v <= n; ++v) {
      if (adj[u][v]) {
        dfs(v);
      }
    }
  }
   
  int main() {
    cin >> n >> m;
   
    vis.resize(n + 1);
    adj.resize(n + 1, vector<bool>(n + 1));
   
    for (int i = 1; i <= m; ++i) {
      int u, v;
      cin >> u >> v;
      adj[u][v] = true;
    }
   
    return 0;
  }

• Python

  vis = [False] * (n + 1)
  adj = [[False] * (n + 1) for _ in range(n + 1)]
   
  for i in range(1, m + 1):
      u, v = map(lambda x: int(x), input().split())
      adj[u][v] = True
   
   
  def find_edge(u, v):
      return adj[u][v]
   
   
  def dfs(u):
      if vis[u]:
          return
      vis[u] = True
      for v in range(1, n + 1):
          if adj[u][v]:
              dfs(v)

复杂度

查询是否存在某条边：$O(1)$。

遍历一个点的所有出边：$O(n)$。

遍历整张图：$O(n^2)$。

空间复杂度：$O(n^2)$。

应用

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 $O(1)$ 查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

邻接表

方法

使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 $u$ 的所有出边的相关信息（终点、边权等）。

参考代码

[list2tab]

• C++

  #include <iostream>
  #include <vector>
   
  using namespace std;
   
  int n, m;
  vector<bool> vis;
  vector<vector<int>> adj;
   
  bool find_edge(int u, int v) {
    for (int i = 0; i < adj[u].size(); ++i) {
      if (adj[u][i] == v) {
        return true;
      }
    }
    return false;
  }
   
  void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
  }
   
  int main() {
    cin >> n >> m;
   
    vis.resize(n + 1);
    adj.resize(n + 1);
   
    for (int i = 1; i <= m; ++i) {
      int u, v;
      cin >> u >> v;
      adj[u].push_back(v);
    }
   
    return 0;
  }

• Python

  vis = [False] * (n + 1)
  adj = [[] for _ in range(n + 1)]
   
  for i in range(1, m + 1):
      u, v = map(lambda x: int(x), input().split())
      adj[u].append(v)
   
   
  def find_edge(u, v):
      for i in range(0, len(adj[u])):
          if adj[u][i] == v:
              return True
      return False
   
   
  def dfs(u):
      if vis[u]:
          return
      vis[u] = True
      for i in range(0, len(adj[u])):
          dfs(adj[u][i])

复杂度

查询是否存在 $u$ 到 $v$ 的边：$O(d^{+}(u))$（如果事先进行了排序就可以使用 二分查找 做到 $O(\log (d^{+}(u)))$）。

遍历点 $u$ 的所有出边：$O(d^{+}(u))$。

遍历整张图：$O(n+m)$。

空间复杂度：$O(m)$。

应用

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

链式前向星

方法

本质上是用数组模拟链表来实现邻接表，采用头插法建立链表。

核心思想

链式前向星使用三个数组来存储图:

• head[u]: 存储节点 u 的第一条边的编号(链表头)
• to[i]: 存储第 i 条边的终点
• nxt[i]: 存储第 i 条边的下一条边的编号(链表的 next 指针)

为什么叫”前向星”?

• 前向: 每次添加新边时，把它插在链表的最前面(头插法)
• 星: 从一个点出发的所有边，像星星一样散开

图解示例

假设依次添加边: 1->2, 1->3, 1->4

初始: head[1]=-1, cnt=-1

添加 1->2 (cnt=0):
  head[1]=0, to[0]=2, nxt[0]=-1
  链表: head[1] → [边0:1->2] → NULL

添加 1->3 (cnt=1):
  head[1]=1, to[1]=3, nxt[1]=0  // 新边指向旧的第一条边
  链表: head[1] → [边1:1->3] → [边0:1->2] → NULL

添加 1->4 (cnt=2):
  head[1]=2, to[2]=4, nxt[2]=1  // 新边又指向旧的第一条边
  链表: head[1] → [边2:1->4] → [边1:1->3] → [边0:1->2] → NULL

遍历时从 head[1]=2 开始，依次访问边2→边1→边0，输出终点: 4→3→2

核心代码

[list2tab]

• C++

  // head[u] 和 cnt 的初始值都为 -1
  void add(int u, int v) {
    nxt[++cnt] = head[u];  // 当前边的后继(指向旧的第一条边)
    head[u] = cnt;         // 更新起点 u 的第一条边为当前边
    to[cnt] = v;           // 当前边的终点
  }
   
  // 遍历 u 的出边
  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
    int v = to[i];  // v 是边 i 的终点
    // 处理边 u->v (边编号为 i)
  }

• Python

  # head[u] 和 cnt 的初始值都为 -1
  def add(u, v):
      cnt = cnt + 1
      nex[cnt] = head[u]  # 当前边的后继
      head[u] = cnt  # 起点 u 的第一条边
      to[cnt] = v  # 当前边的终点
   
   
  # 遍历 u 的出边
  i = head[u]
  while ~i:  # ~i 表示 i != -1
      v = to[i]
      i = nxt[i]

参考代码

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<bool> vis;
vector<int> head, nxt, to;
 
void add(int u, int v) {
  nxt.push_back(head[u]);
  head[u] = to.size();
  to.push_back(v);
}
 
bool find_edge(int u, int v) {
  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
    if (to[i] == v) {
      return true;
    }
  }
  return false;
}
 
void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);
}
 
int main() {
  cin >> n >> m;
 
  vis.resize(n + 1, false);
  head.resize(n + 1, -1);
 
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v);
  }
 
  return 0;
}

复杂度

查询是否存在 $u$ 到 $v$ 的边：$O(d^{+}(u))$。

遍历点 $u$ 的所有出边：$O(d^{+}(u))$。

遍历整张图：$O(n+m)$。

空间复杂度：$O(m)$。

应用

存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。

优点

1. 边有编号: 每条边都有唯一的编号 cnt，这在网络流等算法中很有用
2. 反向边技巧: 如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于 网络流）

   // cnt 初始值为 1 (奇数)
   add(u, v);  // 添加正向边，编号为偶数
   add(v, u);  // 添加反向边，编号为奇数
   // 对于边 i，i^1 就是它的反向边

3. 空间连续: 使用数组而不是真正的链表，缓存友好，常数更小
4. 空间固定: 可以预先分配空间，避免动态分配的开销

与 vector 邻接表对比

使用场景

适合使用链式前向星:

• 边数已知，可以预分配空间
• 网络流算法（需要反向边 i^1）
• 需要边编号的场景
• 卡常数的竞赛题（数组比 vector 快）

建议使用 vector 邻接表:

• 边数未知或变化较大
• 需要对出边排序
• 代码可读性优先
• 不需要边编号

带权边的实现

struct Edge {
    int to, w, nxt;  // 终点、权值、下一条边
};
Edge edge[MAXM];
int head[MAXN], cnt = -1;
 
void add(int u, int v, int w) {
    edge[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}
 
// 遍历
for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    int w = edge[i].w;
}