graph storage

author: Ir1d, sshwy, Xeonacid, partychicken, Anguei, HeRaNO In OI, before operating on a graph, you first need to learn how graphs are stored.

Conventions

This article assumes that you have read and understood the basic material in Graph-theoretic concepts. If you encounter difficulties, you can consult Graph-theoretic concepts as well.

Throughout this article, $n$ denotes the number of vertices, $m$ the number of edges, and $d^+(u)$ the out-degree of vertex $u$, that is, the number of edges leaving $u$.

Direct edge storage

Method

Use an array to store edges, where each element contains the start and end vertices of an edge (and, for a weighted graph, its weight). Alternatively, use separate arrays for the start vertex, end vertex, and edge weight.

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

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 an edge exists: $O(m)$.

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

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

Space complexity: $O(m)$.

Applications

Because traversing a directly stored edge list is inefficient, it is generally not used to traverse a graph.

In Kruskal's algorithm, edges must be sorted by weight, so direct edge storage is necessary.

Some problems require building multiple graphs, such as the original graph and its reverse. In that case, you can use several other data structures to store the graphs simultaneously, or store the edges directly and rebuild each graph from the saved edges when needed.

Adjacency matrix

Method

Use a two-dimensional array adj to store edges. adj[u][v] equal to 1 indicates an edge from $u$ to $v$, while 0 indicates that no such edge exists. In a weighted graph, adj[u][v] can store the weight of the edge from $u$ to $v$.

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

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 an 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)$.

Applications

An adjacency matrix is suitable only when there are no parallel edges, or when parallel edges can be ignored.

Its most significant advantage is that it can answer whether an edge exists in $O(1)$ time.

Because adjacency matrices are inefficient for sparse graphs, especially when the graph has many vertices and the space requirement is prohibitive, they are generally used only for dense graphs.

Adjacency list

Method

Use an array whose elements are stored in a data structure supporting dynamic insertion, such as vector<int> adj[n + 1]. Here adj[u] stores information about all edges leaving vertex $u$, such as their endpoints and weights.

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

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 the list is sorted, binary search gives $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)$.

Applications

Adjacency lists are suitable for almost all graphs, except when there is a special requirement such as fast edge-existence queries on a graph with few vertices, where an adjacency matrix may be preferable.

They are particularly suitable when the outgoing edges of a vertex need to be sorted.

Linked forward star

Method

This is essentially an adjacency list implemented with linked lists. The core code is:

C++

// The initial values of head[u] and cnt are both -1.
void add(int u, int v) {
  nxt[++cnt] = head[u];  // successor of the current edge
  head[u] = cnt;         // first edge leaving u
  to[cnt] = v;           // endpoint of the current edge
}

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

Python

# The initial values of head[u] and cnt are both -1.
def add(u, v):
    cnt = cnt + 1
    nex[cnt] = head[u]  # successor of the current edge
    head[u] = cnt  # first edge leaving u
    to[cnt] = v  # endpoint of the current edge

# Traverse the outgoing edges of u.
i = head[u]
while ~i:  # ~i means 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 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)$.

Applications

This representation is suitable for all kinds of graphs, but it cannot answer edge-existence queries quickly or conveniently sort the outgoing edges of a vertex.

Its advantage is that edges have indices, which can be useful. If the initial value of cnt is odd, then when storing both directions of each edge, i ^ 1 is the reverse edge of i (commonly used in network flow).