首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >查找有向图上是否存在从v到t的非简单路径。

问查找有向图上是否存在从v到t的非简单路径。
EN

Stack Overflow用户
提问于 2014-04-28 15:18:25
回答 2查看 447关注 0票数 1

我在搜索最简单的算法,它可以判断(返回真还是假),如果在给定有向图的顶点v和t之间有一个非简单的路径。

我不介意使用BFS、DFS、Dijkstra或任何其他可以帮助解决这个问题的算法,我试图得到SCC图,但是我找不到它的任何好的用途。

任何帮助都将不胜感激!

谢谢!

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-04-28 15:29:41

Step 0:如果没有从v到t的路径,那么答案是否定的。

Step 1:将G的所有强连通分量折叠后生成图G‘。

Step 2:如果顶点'v‘是由多个顶点组成的SCC的一部分,那么一定存在一个非简单的路径。同样,如果顶点t‘是由多个顶点组成的SCC的一部分,则回答是肯定的。

Step 3:如果step2不是真的话。然后确定图G‘中是否存在从v到t的任何路径,该路径通过折叠成两个或多个顶点的强连通分量的顶点。如果是的话,答案是肯定的,否则答案是否定的。

运行时间: O(M+N),用于上述算法中的每个步骤。因此,总体上是O(M+N)。

编辑:关于如何在线性时间内执行步骤3:

对于G‘中的每个顶点,保持两样东西:

  1. 那个顶点的大小。(不。为这个SCC顶点收缩的G的顶点)
  2. 这个顶点是否可以从t到达。(我们可以从G‘的反图t中运行dfs来计算这一点)

现在,如果存在从G‘中的顶点’顶点‘到通过大小为throughSCC 2的任何SCC顶点的顶点t的路径,下面的函数>= (int顶点)将返回true。函数的伪代码:

代码语言:javascript
复制
boolean throughSCC(int vertex){
    if(!reachable[vertex]){
        return false;
    }
    if(sz[vertex] >= 2){
        return true;
    }
    for(all neighbours X of vertex){
         if(throughSCC(X)){
              return true;
         }
    }
    return false;
}
票数 3
EN

Stack Overflow用户

发布于 2014-04-28 19:43:05

由于SCC算法有点烦人,下面是另一种算法。遍历一次,以确定哪些顶点可以从t向后遍历,忽略从v到不到的顶点,寻找循环。报告一个非简单路径的存在当且仅当这样一个循环被发现。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/23344859

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档