Skip to content

Graph Storage

In OI, to perform operations on graphs, one must first learn how to store graphs.

Convention

This article assumes the reader has already read and understood the basic content in Graph Theory Related Concepts. If difficulties are encountered while reading, one may also refer to Graph Theory Related Concepts.

In this article, \(n\) denotes the number of vertices in the graph, \(m\) denotes the number of edges, and \(d^+(u)\) denotes the out-degree of vertex \(u\), i.e., the number of edges starting from \(u\).

Direct Edge Storage

Method

Use an array to store edges, where each element in the array contains the start and end points of an edge (for weighted graphs, the edge weight is also included). (Alternatively, use multiple arrays to store the start points, end points, and edge weights separately.)

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)

Complexity

Query whether a specific edge exists: \(O(m)\).

Traverse all outgoing edges of a vertex: \(O(m)\).

Traverse the entire graph: \(O(nm)\).

Space complexity: \(O(m)\).

Application

Due to the low efficiency of traversal with direct edge storage, it is generally not used for graph traversal.

In Kruskal's algorithm, since edges need to be sorted by weight, direct edge storage is required.

In some problems, multiple graphs need to be constructed (e.g., constructing the original graph and its reverse graph). In such cases, one can either use multiple other data structures to store multiple graphs simultaneously or store the edges directly and reconstruct the graph using the stored edges when needed.

Adjacency Matrix

Method

Use a two-dimensional array adj to store edges, where adj[u][v] is 1 if there is an edge from \(u\) to \(v\), and 0 otherwise. For weighted graphs, adj[u][v] can store the weight of the edge from \(u\) to \(v\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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)

Complexity

Query whether a specific edge exists: \(O(1)\).

Traverse all outgoing edges of a vertex: \(O(n)\).

Traverse the entire graph: \(O(n^2)\).

Space complexity: \(O(n^2)\).

Application

Adjacency matrices are only suitable for graphs without multiple edges (or where multiple edges can be ignored).

Their most significant advantage is the ability to query whether an edge exists in \(O(1)\).

Since adjacency matrices are inefficient on sparse graphs (especially on graphs with many vertices, where space becomes unmanageable), they are generally used only on dense graphs.

Adjacency List

Method

Use an array of data structures that support dynamic element addition, such as vector<int> adj[n + 1], to store edges. Here, adj[u] stores all relevant information (destination, edge weight, etc.) about the outgoing edges of vertex \(u\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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])

Complexity

Query whether an edge from \(u\) to \(v\) exists: \(O(d^+(u))\) (if sorted in advance, binary search can achieve \(O(\log(d^+(u)))\)).

Traverse all outgoing edges of vertex \(u\): \(O(d^+(u))\).

Traverse the entire graph: \(O(n+m)\).

Space complexity: \(O(m)\).

Application

Suitable for storing various types of graphs, unless there are special requirements (e.g., needing to quickly query whether an edge exists with a small number of vertices, in which case an adjacency matrix can be used).

Particularly suitable for scenarios where the outgoing edges of a vertex need to be sorted.

Linked Forward Star

Method

Essentially, it is an adjacency list implemented using linked lists. The core code is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// head[u] and cnt are initially -1
void add(int u, int v) {
  nxt[++cnt] = head[u];  // successor of the current edge
  head[u] = cnt;         // first edge starting from u
  to[cnt] = v;           // destination of the current edge
}

// traverse outgoing edges of u
for (int i = head[u]; ~i; i = nxt[i]) {  // ~i means i != -1
  int v = to[i];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# head[u] and cnt are initially -1
def add(u, v):
    cnt = cnt + 1
    nex[cnt] = head[u]  # successor of the current edge
    head[u] = cnt  # first edge starting from u
    to[cnt] = v  # destination of the current edge


# traverse outgoing edges of u
i = head[u]
while ~i:  # ~i means i != -1
    v = to[i]
    i = nxt[i]
Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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 means 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;
}

Complexity

Query whether an edge from \(u\) to \(v\) exists: \(O(d^+(u))\).

Traverse all outgoing edges of vertex \(u\): \(O(d^+(u))\).

Traverse the entire graph: \(O(n+m)\).

Space complexity: \(O(m)\).

Application

Suitable for storing various types of graphs, but cannot quickly query whether an edge exists or conveniently sort the outgoing edges of a vertex.

The advantage is that edges are numbered, which can be very useful in some cases. Moreover, if the initial value of cnt is odd, i ^ 1 is the reverse edge of i when storing bidirectional edges (commonly used in network flow).

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用