适用于网络流算法的图形表示

2 回答

• 3

  我会将Ivaylo的表述描述为“边缘连续” . 还有一个“ endpoints 连续”的表示，我相信这是一个非常不科学的样本，可以广泛使用 . 我已经在不同的时间实现了这两个 .

  如果没有硬数据，我的假设是 endpoints 连续表示对于通常的可疑网络流算法比边缘连续表示更好，因为边缘连续每次扫描弧时都会产生随机访问，并且 endpoints 连续，每次流动都被推到弧上（可能是在扫描弧之前） . 这种表示的明显优势在于它支持非对称图（与网络流不太相关） . 这种表示的明显缺点是改变图的拓扑结构要慢得多 .

  该表示由两个数组组成 . first ，n 1个元素，存储具有指定尾部的第一个弧的索引 . 额外的条目是m，弧的总数，因此具有尾部v的弧的索引是 first[v] 包括通过 first[v+1] exclusive . 在Ivaylo的图上，

  [0] = 0->1, [1] = 0->2,
  [2] = 1->0, [3] = 1->2, [4] = 1->3,
  [5] = 2->0, [6] = 2->1, [7] = 2->3, [8] = 2->4,
  [9] = 3->1, [10] = 3->2, [11] = 3->5,
  [12] = 4->2, [13] = 4->5,
  [14] = 5->3, [15] = 5->4,
  

  数组 first 是

  0, 2, 5, 9, 12, 14, 16.
  

  弧本身存储在以下结构类型的m元素数组中 .

  struct Arc {
      int head;
      int capacity;
      int symmetric;
  };
  

  symmetric 是对称弧的索引 .

  回复于 2024-05-03T14:02:19+08:00
• 2

  我使用的表示有点是边列表和邻居列表之间的混合 . 它没有我所知道的官方名称所以我不会说出它的名字 . 它设法满足上述所有要求，并且只需要使用数组 - 这种结构存在于大多数（如果不是全部）流行的编程语言中 . 我将使用 c++ 作为插图，但代码应该可以轻松翻译成其他语言 . 对于这个答案，我将假设顶点编号为 0 至 N-1 ，并且我们的图形具有 M 边缘 .

  我们存储的图表将被定向为处理网络流时通常边缘和其反向边缘具有不同的容量（和这些容量总和到边缘的初始容量 .

  边缘

  当我们处理网络流算法时，每个边缘都有容量（ cap ） . 此外，对于每个边缘，我将存储其目标顶点（ to ）和另一个我将调用 next 的值 . 我们还可以选择添加源顶点，但由于图形的表示方式，因此不需要它 . 我将假设所有这些值都适合 int 类型：

  struct edge {
    // destination vertex
    int to;
    // capacity
    int cap;
    // next edge
    int next;
  };
  

  存储图表

  我将所有边存储在一个数组中，此外我还有一个数组，其中我存储每个顶点的邻居列表的"head"元素 . 我将使用"head"元素命名数组 first . first 应该用一些不是有效顶点数的值初始化，例如-1：

  int first[N];
  // in c++ we can also use memset
  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
  

  让我们添加边缘0 - > 2，容量为7.我将分开两个步骤 - 添加直边和反边：

  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) - 我们的 edges 大小为 M*2 ， first 大小为 N . 当然 N < M 对于任何合理的图形，因此总体内存复杂度为 O(M) . 此外，内存消耗将比使用邻居列表的哈希映射的解决方案的内存消耗少（至少两倍） .

  摘要

  此图表表示以最佳可能的复杂性实现所有必需的操作，并且它几乎没有内存开销 . 表示的另一个优点是它只使用了大多数语言内置的非常基本的结构 - 数组 . 该结构也可以用于其他算法，但是快速访问反向边缘对于图算法特别有用 .

  回复于 2024-05-03T14:02:19+08:00