强连通有向图是有向图,其中对于每两个顶点,并且存在从...到的直接路径以及从到的直接路径.令=(,)是强连通的有向图,并且let =(,)∈是图中的边.设计一种有效的算法,决定是否'=(,∖{}),没有边缘的图是强连接的.解释其正确性并分析其运行时间.
所以我所做的就是运行BFS并对标签求和,一次在原始图形上,然后再在G'中没有边缘(再次从)然后:如果第二个总和(在G'中)<原始总和(在G中)那么图表没有强烈连接.
PS这是我考试中的一个问题,我只得到3/13分,我想知道我是否应该上诉...
algorithm breadth-first-search graph-algorithm strongly-connected-graph