我需要检查有向图是否强连接,或者换句话说,是否所有节点都可以到达任何其他节点(不一定是通过直接边缘).
一种方法是在每个节点上运行DFS和BFS,并查看所有其他节点仍然可访问.
有没有更好的方法来做到这一点？
我正在阅读关于BFS和DFS的图算法.当我分析通过DFS在Graph中查找强连通分量的算法时,我想到了一个疑问.为了找到强连通分量,什么书(Coremen)做,首先它在图上运行DFS以获得顶点的结束时间然后再次按照完成时间的降序在图的转置上运行DFS我们从第一个DFS得到的.但是我无法理解为什么第二个DFS必须按照完成时间运行.我的意思是即使我们直接在图的转置上运行DFS(忽略完成时间),它是否也给了我们连接的组件,因为通过转置我们已经阻止了到其他组件的路径.
我试图找到一种算法来在无向连通图中找到子图，其中子图中的每个顶点都有一条到子图中每个其他顶点的边。
我真正的问题是我无法对这个问题进行分类，因此我可以研究可能的算法或解决方案。
有谁知道这个问题叫什么，或者是否有任何现有的算法可以实现这一目标？