我在搜索最简单的算法,它可以判断(返回真还是假),如果在给定有向图的顶点v和t之间有一个非简单的路径。
我不介意使用BFS、DFS、Dijkstra或任何其他可以帮助解决这个问题的算法,我试图得到SCC图,但是我找不到它的任何好的用途。
任何帮助都将不胜感激!
谢谢!
发布于 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‘中的每个顶点,保持两样东西:
现在,如果存在从G‘中的顶点’顶点‘到通过大小为throughSCC 2的任何SCC顶点的顶点t的路径,下面的函数>= (int顶点)将返回true。函数的伪代码:
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;
}发布于 2014-04-28 19:43:05
由于SCC算法有点烦人,下面是另一种算法。遍历一次,以确定哪些顶点可以从t向后遍历,忽略从v到不到的顶点,寻找循环。报告一个非简单路径的存在当且仅当这样一个循环被发现。
https://stackoverflow.com/questions/23344859
复制相似问题