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

Question

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

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

我们得到了一个有向图，我们必须计算节点的数量 - 从顶点 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
 }  

}

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

Count number of Node - Disjoint Paths between any two nodes in directed graph such that there distance is <=K

algorithm

graph-theory

depth-first-search

breadth-first-search

directed-graph