Tarjan算法是在无线性图中以线性时间运行的第一个桥梁查找算法。但是，存在一种更简单的算法，您可以在此处查看其实现。
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]); } }该算法通过维持2个数组的前和下进行工作。pre保留节点的遍历遍历编号。因此pre [0] = 2表示在第3个dfs调用中发现了顶点0。low[u]保持可从u到达的所有顶点中的最小序数。
每当边缘u–v时，该算法都会检测到一个桥，其中u在预序编号low [v] == pre[v]中排名第一。这是因为，如果我们删除u–v之间的边，v将无法到达u之前的任何顶点。因此，删除边缘会将图分成2个单独的图。
