algorithm - 计算节点数 - 有向图中任意两个节点之间的不相交路径，使得距离 <= K

Question

我们如何计算节点数 - 任意两个节点之间的不相交路径使得两个节点之间的距离最大K？

有关节点的详细信息 - 不相交路径可以是 found here .

我们得到一个有向图，其中我们必须计算节点的数量 - 从顶点 u 到 v 的不相交路径使得它们之间的最大节点数为 K - 2(u 和 v 从 K 递减，因此 K - 2)。图中的顶点数最多可达10^5，边数可达6 * 10^5。我想为每个节点实现 BFS，直到与源节点的最大距离小于 K。但我没有实现的想法。有人可以帮帮我吗？

如果有人有使用 DFS 解决它的想法，请分享。

Answer 1

DFS 是解决这类问题的关键。我们可以使用 DFS 轻松枚举 2 个顶点之间的所有可能路径，但我们必须注意距离约束。

我的算法将遍历的边数视为约束条件。您可以轻松地将其转换为遍历的节点数。把它当作练习。

我们跟踪变量 e 遍历的边数。如果 e 变得大于 K - 2，我们将终止该递归 DFS 调用。

为了保持顶点已被访问，我们保留了一个boolean 数组visited。但是，如果递归调用在没有找到成功路径的情况下终止，我们将放弃对数组 visited 所做的任何更改。

只有当递归 DFS 调用成功找到路径时，我们才会为程序的其余部分保留 visited 数组。

所以算法的伪代码是:

main function()
{
 visited[source] = 1     
 e = 0//edges traversed so far.
 sum = 0// the answer
 found = false// found a path.
 dfs(source,e)
 print sum
 .
 .
 .
}

dfs(source,e)
{
 if(e > max_distance)
 {      
  return
 }

 if(e <= max_distance and v == destination)
 {
  found = true
  sum++      
  return
 }

 for all unvisited neighbouring vertices X of v
 {
  if(found and v != source)
   return;
  if(found and v == source)
  {
   found = false
   visited[destination] = 0
  }

  visited[X] = 1
  dfs(X , e + 1)
  if(!found)
   visited[X] = 1
 }  

}