本质上是用链表实现的邻接表。

以每个节点为表头创建链表

每个链表的第一位为当个节点

往后的元素都是该节点的出度或者入度，也可以通过建立一个逆邻接表来同时存储二者。

下文为OIwiki的核心实现代码

1
2
3
4
5
6
7
8
9
10
11
// 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];
}

`

以及完整实现代码

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(); //使head[u]指向to中v的位置所在
  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;
}

但是笔者更加习惯于使用结构体

如下构造结构体

1
2
3
4
5
6
7
8
struct Edge
{
    int to, w, next;//next存储上一条边的编号
    
}edge[maxn];

int head[maxn];
//标志着以i节点的出度的链表下第一条边

初始化部分略过

添加边代码如下

1
2
3
4
5
6
7
void add(int u, int v,int w)
{
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}

查询节点出度代码如下

1
2
3
4
5
6
7
void Find(int u)
{
    for(int i = head[u]; i~； i = edge[i].next)
    {
        cout << edge[i].to << " " << edge[i].w;
    }
}

非常煎蛋实用存储图