图中的桥

Graph

图是其中值存储在节点中，节点通过边相互连接的数据结构。图可以是连通的或不连通的。如果图中存在多个连通分量，则该图称为不连通图。

我们可以使用遍历（BFS 或 DFS）来计算图中的连通分量数量。

图中的桥是那些创建节点唯一路径的边。如果移除一条边会创建一个图，或者将一个图分成多个连通分量，则该边称为桥。

我们将给定图，我们的任务是打印出图中的所有桥（如果存在）。

例如

在上面的示例中，如果您移除节点 2 和 4 之间的边，图将变得不连通，因此它是桥。

方法 1

这个问题的一种暴力解法是，对于每条边，我们移除该边并检查图中的连通分量数量。如果数量多于一个，则我们将该边添加到我们的答案中，然后我们将其重新添加并检查下一条边。

Java 代码

输出

说明

在上面的代码中，我们创建了一个邻接矩阵作为图，并且对于每条边，我们都移除了该边并调用函数来获取连通分量的数量。如果连通分量的数量多于一个，我们将打印当前边作为桥。

为了获得连通分量的数量，我们从节点 0 开始使用 DFS，然后计算我们调用了多少次 DFS 来获得连通分量的数量。

时间复杂度：O(E*(N+E))

空间复杂度：O(1)

方法 2

我们将使用一种基于节点到达的初始时间和最小时间来确定图中的桥边的最优方法。

我们将使用 DFS（深度优先搜索）遍历图，如果节点未被访问，则更新其插入时间和最小时间，然后对未访问的邻居（除了其父节点）调用 DFS。

在对未访问的相邻节点进行 DFS 调用后，我们将更新当前节点的最小时间。如果相邻节点的最小时间大于当前节点的插入时间，则当前节点和相邻节点之间肯定存在桥边，因此我们将打印它。

上述逻辑的原因是，除了经过当前节点之外，没有其他路径可以从当前节点到达相邻节点。

Java 代码

输出

时间复杂度：O(N+E) 用于使用 DFS 遍历图，其中 N 是节点数，E 是图中的边数。

空间复杂度：O(N)+O(N)+O(N) 用于使用三个数组。