图的存储

约定

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

直接存边

实现

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

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:
    u = 0
    v = 0

n, m = map(lambda x:int(x), input().split())

e = [Edge()] * m; vis = [False] * n

for i in range(0, m):
    e[i].u, e[i].v = map(lambda x:int(x), input().split())

def find_edge(u, v):
    for i in range(1, m + 1):
        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(1, m + 1):
        if e[i].u == u:
            dfs(e[i].v)

警告

vector<bool> 的偏特化

我们来看如下的一段代码

#include <iostream>
#include <vector>
using namespace std;
#define _VEC_BOOL_
int main() {
  int count = 0, n = 15000000;
#ifdef _VEC_BOOL_
  vector<bool> isPrime;
  isPrime.reserve(n);
  isPrime.assign(n, true);
#else
  bool* isPrime = new bool[n];
  for (int i = 0; i < n; ++i) {
    isPrime[i] = true;
  }
#endif
  for (int i = 2; i < n; ++i) {
    if (isPrime[i]) {
      count++;
    }
    for (int j = 2; i * j < n; ++j) {
      isPrime[i * j] = false;
    }
  }
  cout << count << endl;
  return 0;
}

如果使用 bool 数组，程序耗时为 0.8 秒， 而使用 vector<bool> 的耗时则变为 5.8 秒

C++ 中的 vector<bool> 为了节省空间， 使用了模板偏特化， 只用一个 bit 来表示一个元素， references 和 iterators 经过了特殊的处理，并不是bool值的实际地址, 因而无论是从内存对齐或 cache miss 的角度考量， 还是从潜在的地址转换的角度考虑， vector<bool> 的时间复杂度表现都是不乐观的， 因为它的实现更像是种时间换空间的做法。

因此如非必要，请避免使用 vector<bool>

使用 std::vector<std::uint8_t> 或直接使用 std::vector<int>

复杂度

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

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

应用

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

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

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

邻接矩阵

实现

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

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, false);
  adj.resize(n + 1, vector<bool>(n + 1, false));

  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 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(n^2)$

操作	时间复杂度
查询是否存在某条边	$O(1)$
遍历一个点的所有出边	$O(n)$
遍历整张图	$O(n^2)$

应用

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

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

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

邻接表

实现

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

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, false);
  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 = [[]] * (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])

复杂度

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

操作	时间复杂度
查询是否存在某条边	$O(d^{+}(u))$
遍历点 $u$ 的所有出边	$O(d^{+}(u))$
遍历整张图	$O(n + m)$

提示

如果事先进行了排序，可以通过二分查找使得"查询是否存在某条边"操作的 复杂度降到 $O( \log (d^{+}(u)) )$

应用

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

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

链式前向星

实现

本质上是用链表实现的邻接表，核心代码如下：

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

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]

复杂度

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

操作	时间复杂度
查询是否存在某条边	$O(d^{+}(u))$
遍历点 $u$ 的所有出边	$O(d^{+}(u))$
遍历整张图	$O(n + m)$

应用

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

优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于 网络流）。