我使用的表示方法是边缘列表和邻居列表的混合体。我不知道它是否有官方名称，所以我不会给它命名。它能够满足上述所有要求，并且只需要使用数组——这是大多数（如果不是全部）流行编程语言中都存在的结构。我将使用进行说明，但代码应该很容易翻译成其他语言。对于本答案，我假设顶点从
0到
N-1编号，我们的图具有
M条边。
我们存储的图将是有向的，因为在处理网络流时，通常边及其反向边具有不同的容量（这些容量加起来等于边的初始容量）。
一条边
由于我们正在处理网络流算法，每条边都有容量(
cap)。除此之外，对于每条边，我将存储其目标顶点(
to)和另一个我称之为
next的值。我们还可以选择添加源顶点，但由于图的表示方式，这不是必需的。我假设所有这些值都适合于
int类型：
struct edge {
int to;
int cap;
int next;
};
存储图
我将所有边存储在一个数组中，此外我还会有一个额外的数组，用于存储每个顶点邻居列表的“头”元素。我将把带有“头”元素的数组命名为first。first应该被初始化为一些不是有效顶点编号的值，例如-1：
int first[N];
for (int i = 0; i < N; ++i) {
first[i] = -1;
}
由于最大网络流算法的实现方式，对于每条边，我们应该添加一条容量为0的反向边。因此，存储边的数组大小实际上是2*M：
edge edges[M * 2];
现在我提出的表示方法有两个关键点：
- 我们形成一个给定顶点的邻居的（单向）链表，并且每个链表的头（第一个）元素的索引存储在数组
first 中。
- 对于每条边，我们在边的数组中紧跟其反向边添加。
向单向链表添加元素只需在
add_edge 函数中略作修改 - 我们还应该添加反向边。为了简化代码，我将假设我们有一个变量
edges_num，它代表我们已经添加的边数，并且我将像全局变量一样使用它。我实现了一个
add_edge 函数，它接受三个参数 - 源顶点、目标顶点和边的容量：
int edges_num = 0;
inline void add_edge(int from, int to, int cap) {
edges[edges_num].to = to;
edges[edges_num].cap = cap;
edges[edges_num].next = first[from];
first[from] = edges_num++;
edges[edges_num].to = from;
edges[edges_num].cap = 0;
edges[edges_num].next = first[to];
first[to] = edges_num++;
}
请注意，反向边的容量通常会被初始化为
0。这基本上就是我们使用这种表示法来存储图所需的全部内容。
一个例子
让我们看看两个数组
first和
edges的内容如何更改：
在添加任何边之前：
first: edges:
0 1 2 3 4 5 []
-1 -1 -1 -1 -1 -1
我们添加容量为7的边0->2。我将分开两个步骤-添加正向边和反向边：
first: edges:
0 1 2 3 4 5 [{to: 2, cap: 7, next: -1}]
0 -1 -1 -1 -1 -1
现在来说反向边：
first: edges:
0 1 2 3 4 5 [{to: 2, cap: 7, next: -1}, {to: 0, cap: 0, next: -1}]
0 -1 1 -1 -1 -1
现在让我们添加0->1（容量为5）：
first: edges:
0 1 2 3 4 5 [{2, 7, -1}, {0, 0, -1}, {1, 5, 0}, {0, 0, -1}]
2 -1 1 -1 -1 -1
请注意，索引为2的边具有下一个值为0，这表明0是具有源0的下一条边。我将继续添加边：
2->1 容量为1：
first: edges:
0 1 2 3 4 5 [{2, 7, -1}, {0, 0, -1}, {1, 5, 0}, {0, 0, -1}, {1, 1, 1},
2 5 4 -1 -1 -1 {2, 0, -1}]
现在，我们快进添加2->3(容量11)，2->4(容量8)，1->3(容量4)，4->5(容量3)和3->5(容量6)，按照相同的顺序：
first: edges:
0 1 2 3 4 5 [{2, 7, -1}, {0, 0, -1}, {1, 5, 0}, {0, 0, -1}, {1, 1, 1},
2 10 8 14 12 15 {2, 0, -1}, {3, 11, 4}, {2, 0, -1}, {4, 8, 6}, {2, 0, -1},
{3, 4, 5}, {1, 0, 7}, {5, 3, 9}, {4, 0, -1}, {5, 6, 11},
{3, 0, 13}]
希望这个示例能清晰地展示表示法的工作原理。
遍历所有相邻顶点
对于给定顶点v的所有相邻顶点进行迭代非常简单 - 只需要遍历一个单链表：
for (int cv = first[v]; cv != -1; cv = edges[cv].next) {
// do something
}
很明显，这个操作在邻居数量上是线性的。
访问反向边
利用反向边总是在直接边之后添加的事实，反向边的索引公式非常简单。在edges中，索引为e的边的反向边是索引为e ^ 1的边。这适用于访问直接边和反向边的反向边。同样，这显然是恒定的，并且非常容易编码。
内存消耗
所需的内存为O(M + N) - 我们有大小为M * 2的edges和大小为N的first。当然，对于任何合理的图形而言，N < M，因此总体内存复杂度为O(M)。此外，内存消耗将比使用哈希映射作为邻居列表的解决方案少得多（至少两倍）。
总结
这种图形表示实现了所有所需的操作，具有最佳可能的复杂性，并且内存开销很小。该表示法的另一个优点是它仅使用了大多数语言内置的非常基本的结构 - 数组。这个结构也可以用于其他算法，但是对图形算法来说，快速访问反向边特别有用。
