我如何在无向图中找到桥梁？

编程入门行业动态更新时间:2024-10-11 19:14:12

本文介绍了我如何在无向图中找到桥梁？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述给定一个无向图，我怎样才能找到所有的桥梁？我只找到了似乎相当复杂的Tarjan算法。

似乎应该有多个线性时间解决方案，但我找不到任何东西。 b $ b

解决方案

Tarjan的算法是在线性时间运行的无向图中的第一个桥寻找算法。然而，一个更简单的算法存在，你可以看看它的实现 here 。

private int bridges; //桥梁的数量 private int cnt; // counter private int [] pre; // pre [v] = dfs检查的顺序v private int [] low; // low [v] =与v 相连的任何顶点的最低预定义公共桥（图G）{ low = new int [G.V（）]; pre = new int [G.V（）]; for（int v = 0; v 该算法通过维护2个数组来完成工作，低。 pre保存节点的预序遍历编号。所以pre [0] = 2意味着在第三次dfs调用中发现了顶点0。并且low [u]保存从u到达的任何顶点的最小预序号。算法检测到一个边缘u - v，其中u在预编号中首先出现，low [v] == pre [v]。这是因为如果我们移除了u - v之间的边，v就无法到达u之前的任何顶点。因此去除边缘会将图分成2个独立的图。

有关更详细的解释，您还可以查看这个答案。

Given an undirected Graph, how can I find all the bridges? I've only found Tarjan's algorithm which seems rather complicated.

It seems there should be multiple linear time solutions, but I can't find anything.

解决方案

Tarjan's algorithm was the first bridge finding algorithm in an undirected graph that ran in linear time. However a simpler algorithm exists and you can have a look at its implementation here.

private int bridges; // number of bridges private int cnt; // counter private int[] pre; // pre[v] = order in which dfs examines v private int[] low; // low[v] = lowest preorder of any vertex connected to v public Bridge(Graph G) { low = new int[G.V()]; pre = new int[G.V()]; for (int v = 0; v < G.V(); v++) low[v] = -1; for (int v = 0; v < G.V(); v++) pre[v] = -1; for (int v = 0; v < G.V(); v++) if (pre[v] == -1) dfs(G, v, v); } public int components() { return bridges + 1; } private void dfs(Graph G, int u, int v) { pre[v] = cnt++; low[v] = pre[v]; for (int w : G.adj(v)) { if (pre[w] == -1) { dfs(G, v, w); low[v] = Math.min(low[v], low[w]); if (low[w] == pre[w]) { StdOut.println(v + "-" + w + " is a bridge"); bridges++; } } // update low number - ignore reverse of edge leading to v else if (w != u) low[v] = Math.min(low[v], pre[w]); } }

The algorithm does the job by maintaining 2 arrays pre and low. pre holds the pre-order traversal numbering for the nodes. So pre[0] = 2 means that vertex 0 was discovered in the 3rd dfs call. And low[u] holds the smallest pre-order number of any vertex that is reachable from u. The algorithm detects a bridge whenever for an edge u--v, where u comes first in the preorder numbering, low[v]==pre[v]. This is because if we remove the edge between u--v, v can't reach any vertex that comes before u. Hence removing the edge would split the graph into 2 separate graphs.