如何处理节点不相交路径的编码

Question

我正在尝试解决有向图中 node/vertices 不相交路径的问题，并且开始了解将节点分别拆分为入节点和出节点的想法。我明白了这个想法及其工作原理以及所有相关定理，例如 menger 定理，但我仍然不确定如何以有效的方式对其进行编码。

我应该使用哪种数据结构来拆分顶点并仍然设法平衡时间复杂度？是否存在任何算法可以告诉如何处理代码。

请帮助或建议一些合适的link，这可能会帮助我。

谢谢

Answer 1

其实很简单。假设您将图形作为对 u v 的边列表，这意味着从 u 到 v

有一条边

如果节点不是整数，则已经使用 dictionary/hash/map 将它们缩减为 1..n 范围内的整数，其中 n 是节点数。
现在我们“拆分”所有节点，对于每个节点i，它将成为2个节点i和i+n。其中 i 被认为是 in-node 和 i+n out-node.
现在修改了图的边，对于每条边 u --> v 我们改为存储边 u+n --> v 我们还添加了从每个节点 in-node 到 out-node 的边，即从节点 i 到 i+n
我们可以将 infinity 容量分配给所有边，将 1 的容量分配给连接 in-node 到 [= 的边44=]外节点
现在可以使用任何最大流算法（Ford-Fulkerson、Edmonds-Karp、Dinic 等）找到从某个节点 s 到 t 的节点不相交路径)

构建残差网络的伪代码：

n = #nodes

for each node i in 1..n:
   residual_graph.addEdge(i, i+n, capacity=1);
   residual_graph.addEdge(i+n, i, capacity=0);

for each edge (u,v) in graph
  residual_graph.addEdge(u+n, v, capacity=+Infinity);
  residual_graph.addEdge(v, u+n, capacity=0);

如何处理节点不相交路径的编码

How to approach coding for node disjoint path

algorithm

graph-theory

disjoint-sets

max-flow