如果移除无向连通图中的边会断开该图，则该边就是桥。对于一个不连通的无向图，定义是类似的，桥是一个边移除，它增加了不连通的组件的数量。 喜欢 关节点 ，网桥代表连接网络中的漏洞，对于设计可靠的网络非常有用。例如，在有线计算机网络中，连接点表示关键计算机，桥接器表示关键电线或连接。
null
下面是一些用红色突出显示桥梁的示例图。
如何找到给定图形中的所有桥？ 一种简单的方法是逐个删除所有边，然后查看删除边是否会导致图断开连接。下面是连通图的简单方法步骤。 1） 对于每个边（u，v），执行以下操作 …..a） 从图形中删除（u，v） …b）查看图表是否保持连接（我们可以使用BFS或DFS） …..c） 将（u，v）添加回图表。 对于用邻接表表示的图，上述方法的时间复杂度为O（E*（V+E））。我们能做得更好吗？
求所有桥的O（V+E）算法 这个想法类似于 关节点的O（V+E）算法 .我们对给定的图进行DFS遍历。在DFS树中，如果不存在从以v为根的子树到达u或u的祖先的任何其他替代方法，则边（u，v）（u是DFS树中v的父）是桥 以前的职位 ，值低[v]表示从以v为根的子树可以到达的最早访问顶点。 边（u，v）成为桥的条件是“低[v]>盘[u]” .
以下是上述方法的实现。
C++
// A C++ program to find bridges in a given undirected graph #include<iostream> #include <list> #define NIL -1 using namespace std; // A class that represents an undirected graph class Graph { int V; // No. of vertices list< int > *adj; // A dynamic array of adjacency lists void bridgeUtil( int v, bool visited[], int disc[], int low[], int parent[]); public : Graph( int V); // Constructor void addEdge( int v, int w); // to add an edge to graph void bridge(); // prints all bridges }; Graph::Graph( int V) { this ->V = V; adj = new list< int >[V]; } void Graph::addEdge( int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } // A recursive function that finds and prints bridges using // DFS traversal // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree void Graph::bridgeUtil( int u, bool visited[], int disc[], int low[], int parent[]) { // A static variable is used for simplicity, we can // avoid use of static variable by passing a pointer. static int time = 0; // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++ time ; // Go through all vertices adjacent to this list< int >::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of u // If v is not visited yet, then recur for it if (!visited[v]) { parent[v] = u; bridgeUtil(v, visited, disc, low, parent); // Check if the subtree rooted with v has a // connection to one of the ancestors of u low[u] = min(low[u], low[v]); // If the lowest vertex reachable from subtree // under v is below u in DFS tree, then u-v // is a bridge if (low[v] > disc[u]) cout << u << " " << v << endl; } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = min(low[u], disc[v]); } } // DFS based function to find all bridges. It uses recursive // function bridgeUtil() void Graph::bridge() { // Mark all the vertices as not visited bool *visited = new bool [V]; int *disc = new int [V]; int *low = new int [V]; int *parent = new int [V]; // Initialize parent and visited arrays for ( int i = 0; i < V; i++) { parent[i] = NIL; visited[i] = false ; } // Call the recursive helper function to find Bridges // in DFS tree rooted with vertex 'i' for ( int i = 0; i < V; i++) if (visited[i] == false ) bridgeUtil(i, visited, disc, low, parent); } // Driver program to test above function int main() { // Create graphs given in above diagrams cout << "Bridges in first graph " ; Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.bridge(); cout << "Bridges in second graph " ; Graph g2(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.bridge(); cout << "Bridges in third graph " ; Graph g3(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.bridge(); return 0; } |
JAVA
// A Java program to find bridges in a given undirected graph import java.io.*; import java.util.*; import java.util.LinkedList; // This class represents a undirected graph using adjacency list // representation class Graph { private int V; // No. of vertices // Array of lists for Adjacency List Representation private LinkedList<Integer> adj[]; int time = 0 ; static final int NIL = - 1 ; // Constructor @SuppressWarnings ( "unchecked" )Graph( int v) { V = v; adj = new LinkedList[v]; for ( int i= 0 ; i<v; ++i) adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge( int v, int w) { adj[v].add(w); // Add w to v's list. adj[w].add(v); //Add v to w's list } // A recursive function that finds and prints bridges // using DFS traversal // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree void bridgeUtil( int u, boolean visited[], int disc[], int low[], int parent[]) { // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++time; // Go through all vertices adjacent to this Iterator<Integer> i = adj[u].iterator(); while (i.hasNext()) { int v = i.next(); // v is current adjacent of u // If v is not visited yet, then make it a child // of u in DFS tree and recur for it. // If v is not visited yet, then recur for it if (!visited[v]) { parent[v] = u; bridgeUtil(v, visited, disc, low, parent); // Check if the subtree rooted with v has a // connection to one of the ancestors of u low[u] = Math.min(low[u], low[v]); // If the lowest vertex reachable from subtree // under v is below u in DFS tree, then u-v is // a bridge if (low[v] > disc[u]) System.out.println(u+ " " +v); } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = Math.min(low[u], disc[v]); } } // DFS based function to find all bridges. It uses recursive // function bridgeUtil() void bridge() { // Mark all the vertices as not visited boolean visited[] = new boolean [V]; int disc[] = new int [V]; int low[] = new int [V]; int parent[] = new int [V]; // Initialize parent and visited, and ap(articulation point) // arrays for ( int i = 0 ; i < V; i++) { parent[i] = NIL; visited[i] = false ; } // Call the recursive helper function to find Bridges // in DFS tree rooted with vertex 'i' for ( int i = 0 ; i < V; i++) if (visited[i] == false ) bridgeUtil(i, visited, disc, low, parent); } public static void main(String args[]) { // Create graphs given in above diagrams System.out.println( "Bridges in first graph " ); Graph g1 = new Graph( 5 ); g1.addEdge( 1 , 0 ); g1.addEdge( 0 , 2 ); g1.addEdge( 2 , 1 ); g1.addEdge( 0 , 3 ); g1.addEdge( 3 , 4 ); g1.bridge(); System.out.println(); System.out.println( "Bridges in Second graph" ); Graph g2 = new Graph( 4 ); g2.addEdge( 0 , 1 ); g2.addEdge( 1 , 2 ); g2.addEdge( 2 , 3 ); g2.bridge(); System.out.println(); System.out.println( "Bridges in Third graph " ); Graph g3 = new Graph( 7 ); g3.addEdge( 0 , 1 ); g3.addEdge( 1 , 2 ); g3.addEdge( 2 , 0 ); g3.addEdge( 1 , 3 ); g3.addEdge( 1 , 4 ); g3.addEdge( 1 , 6 ); g3.addEdge( 3 , 5 ); g3.addEdge( 4 , 5 ); g3.bridge(); } } // This code is contributed by Aakash Hasija |
Python3
# Python program to find bridges in a given undirected graph #Complexity : O(V+E) from collections import defaultdict #This class represents an undirected graph using adjacency list representation class Graph: def __init__( self ,vertices): self .V = vertices #No. of vertices self .graph = defaultdict( list ) # default dictionary to store graph self .Time = 0 # function to add an edge to graph def addEdge( self ,u,v): self .graph[u].append(v) self .graph[v].append(u) '''A recursive function that finds and prints bridges using DFS traversal u --> The vertex to be visited next visited[] --> keeps track of visited vertices disc[] --> Stores discovery times of visited vertices parent[] --> Stores parent vertices in DFS tree''' def bridgeUtil( self ,u, visited, parent, low, disc): # Mark the current node as visited and print it visited[u] = True # Initialize discovery time and low value disc[u] = self .Time low[u] = self .Time self .Time + = 1 #Recur for all the vertices adjacent to this vertex for v in self .graph[u]: # If v is not visited yet, then make it a child of u # in DFS tree and recur for it if visited[v] = = False : parent[v] = u self .bridgeUtil(v, visited, parent, low, disc) # Check if the subtree rooted with v has a connection to # one of the ancestors of u low[u] = min (low[u], low[v]) ''' If the lowest vertex reachable from subtree under v is below u in DFS tree, then u-v is a bridge''' if low[v] > disc[u]: print ( "%d %d" % (u,v)) elif v ! = parent[u]: # Update low value of u for parent function calls. low[u] = min (low[u], disc[v]) # DFS based function to find all bridges. It uses recursive # function bridgeUtil() def bridge( self ): # Mark all the vertices as not visited and Initialize parent and visited, # and ap(articulation point) arrays visited = [ False ] * ( self .V) disc = [ float ( "Inf" )] * ( self .V) low = [ float ( "Inf" )] * ( self .V) parent = [ - 1 ] * ( self .V) # Call the recursive helper function to find bridges # in DFS tree rooted with vertex 'i' for i in range ( self .V): if visited[i] = = False : self .bridgeUtil(i, visited, parent, low, disc) # Create a graph given in the above diagram g1 = Graph( 5 ) g1.addEdge( 1 , 0 ) g1.addEdge( 0 , 2 ) g1.addEdge( 2 , 1 ) g1.addEdge( 0 , 3 ) g1.addEdge( 3 , 4 ) print ( "Bridges in first graph " ) g1.bridge() g2 = Graph( 4 ) g2.addEdge( 0 , 1 ) g2.addEdge( 1 , 2 ) g2.addEdge( 2 , 3 ) print ( "Bridges in second graph " ) g2.bridge() g3 = Graph ( 7 ) g3.addEdge( 0 , 1 ) g3.addEdge( 1 , 2 ) g3.addEdge( 2 , 0 ) g3.addEdge( 1 , 3 ) g3.addEdge( 1 , 4 ) g3.addEdge( 1 , 6 ) g3.addEdge( 3 , 5 ) g3.addEdge( 4 , 5 ) print ( "Bridges in third graph " ) g3.bridge() #This code is contributed by Neelam Yadav |
C#
// A C# program to find bridges // in a given undirected graph using System; using System.Collections.Generic; // This class represents a undirected graph // using adjacency list representation public class Graph { private int V; // No. of vertices // Array of lists for Adjacency List Representation private List< int > []adj; int time = 0; static readonly int NIL = -1; // Constructor Graph( int v) { V = v; adj = new List< int >[v]; for ( int i = 0; i < v; ++i) adj[i] = new List< int >(); } // Function to add an edge into the graph void addEdge( int v, int w) { adj[v].Add(w); // Add w to v's list. adj[w].Add(v); //Add v to w's list } // A recursive function that finds and prints bridges // using DFS traversal // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree void bridgeUtil( int u, bool []visited, int []disc, int []low, int []parent) { // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++time; // Go through all vertices adjacent to this foreach ( int i in adj[u]) { int v = i; // v is current adjacent of u // If v is not visited yet, then make it a child // of u in DFS tree and recur for it. // If v is not visited yet, then recur for it if (!visited[v]) { parent[v] = u; bridgeUtil(v, visited, disc, low, parent); // Check if the subtree rooted with v has a // connection to one of the ancestors of u low[u] = Math.Min(low[u], low[v]); // If the lowest vertex reachable from subtree // under v is below u in DFS tree, then u-v is // a bridge if (low[v] > disc[u]) Console.WriteLine(u + " " + v); } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = Math.Min(low[u], disc[v]); } } // DFS based function to find all bridges. It uses recursive // function bridgeUtil() void bridge() { // Mark all the vertices as not visited bool []visited = new bool [V]; int []disc = new int [V]; int []low = new int [V]; int []parent = new int [V]; // Initialize parent and visited, // and ap(articulation point) arrays for ( int i = 0; i < V; i++) { parent[i] = NIL; visited[i] = false ; } // Call the recursive helper function to find Bridges // in DFS tree rooted with vertex 'i' for ( int i = 0; i < V; i++) if (visited[i] == false ) bridgeUtil(i, visited, disc, low, parent); } // Driver code public static void Main(String []args) { // Create graphs given in above diagrams Console.WriteLine( "Bridges in first graph " ); Graph g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.bridge(); Console.WriteLine(); Console.WriteLine( "Bridges in Second graph" ); Graph g2 = new Graph(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.bridge(); Console.WriteLine(); Console.WriteLine( "Bridges in Third graph " ); Graph g3 = new Graph(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.bridge(); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // A Javascript program to find bridges in a given undirected graph // This class represents a directed graph using adjacency // list representation class Graph { // Constructor constructor(v) { this .V = v; this .adj = new Array(v); this .NIL = -1; this .time = 0; for (let i=0; i<v; ++i) this .adj[i] = []; } //Function to add an edge into the graph addEdge(v,w) { this .adj[v].push(w); //Note that the graph is undirected. this .adj[w].push(v); } // A recursive function that finds and prints bridges // using DFS traversal // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree bridgeUtil(u,visited,disc,low,parent) { // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++ this .time; // Go through all vertices adjacent to this for (let i of this .adj[u]) { let v = i; // v is current adjacent of u // If v is not visited yet, then make it a child // of u in DFS tree and recur for it. // If v is not visited yet, then recur for it if (!visited[v]) { parent[v] = u; this .bridgeUtil(v, visited, disc, low, parent); // Check if the subtree rooted with v has a // connection to one of the ancestors of u low[u] = Math.min(low[u], low[v]); // If the lowest vertex reachable from subtree // under v is below u in DFS tree, then u-v is // a bridge if (low[v] > disc[u]) document.write(u+ " " +v+ "<br>" ); } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = Math.min(low[u], disc[v]); } } // DFS based function to find all bridges. It uses recursive // function bridgeUtil() bridge() { // Mark all the vertices as not visited let visited = new Array( this .V); let disc = new Array( this .V); let low = new Array( this .V); let parent = new Array( this .V); // Initialize parent and visited, and ap(articulation point) // arrays for (let i = 0; i < this .V; i++) { parent[i] = this .NIL; visited[i] = false ; } // Call the recursive helper function to find Bridges // in DFS tree rooted with vertex 'i' for (let i = 0; i < this .V; i++) if (visited[i] == false ) this .bridgeUtil(i, visited, disc, low, parent); } } // Create graphs given in above diagrams document.write( "Bridges in first graph <br>" ); let g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.bridge(); document.write( "<br>" ); document.write( "Bridges in Second graph<br>" ); let g2 = new Graph(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.bridge(); document.write( "<br>" ); document.write( "Bridges in Third graph <br>" ); let g3 = new Graph(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.bridge(); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Bridges in first graph3 40 3Bridges in second graph2 31 20 1Bridges in third graph1 6
时间复杂性： 上面的函数是带有附加数组的简单DFS。因此，对于图的邻接表表示，时间复杂度与DFS相同，DFS是O（V+E）。
参考资料： https://www.cs.washington.edu/education/courses/421/04su/slides/artic.pdf http://www.slideshare.net/TraianRebedea/algorithm-design-and-complexity-course-8 http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L25-Connectivity.htm http://www.youtube.com/watch?v=bmyyxNyZKzI 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.cppku.com/wp-content/themes/zibll/img/thumbnail.svg)
