如何找到给定图(graph)中的所有桥（） _图的桥

本文概述

C ++
Java
python
C#

无向连通图中的一条边是断开该图的桥。对于一个断开的无向图，它的定义是类似的，桥是一个删除边缘，增加断开组件的数量。
像连接点一样，桥表示连接网络中的漏洞，对于设计可靠的网络非常有用。例如，在有线计算机网络中，一个连接点表示关键计算机，一个桥表示关键导线或连接。
以下是一些带有红色突出显示的桥的示例图。

文章图片

文章图片
如何找到给定图中的所有桥？
一种简单的方法是一个接一个地删除所有边, 并查看是否删除边会导致图形断开。以下是连接图的简单方法步骤。
1)对于每个边(u, v), 请执行以下操作
…..a)从图表中删除(u, v)
..…b)查看图形是否保持连接状态(我们可以使用BFS或DFS)
…..c)将(u, v)添加回图形。
对于使用邻接表表示的图, 上述方法的时间复杂度为O(E *(V + E))。我们可以做得更好吗？
O(V + E)算法查找所有桥梁
其思想类似于O(V+E)算法的衔接点。我们对给定的图做DFS遍历。在DFS树中，一条边(u, v) (u在DFS树中是v的父)是桥，如果没有任何其他的选择可以到达u或者以v为根的子树到达u的祖先。
正如前一篇文章所讨论的，low[v]表示从以v为根的子树中可以到达的最早访问的顶点。边(u, v)成为桥的条件是:“low[v] > disc[u]”。
以下是上述方法的C ++和Java实现。
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 tract 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 aadjacent 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 isbelow 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 < < "\nBridges in first graph \n" ; 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 < < "\nBridges in second graph \n" ; Graph g2(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.bridge(); cout < < "\nBridges in third graph \n" ; 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// Arrayof lists for Adjacency List Representation private LinkedList< Integer> adj[]; int time = 0 ; static final int NIL = - 1 ; // Constructor 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 tract 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 aadjacent 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

python

# 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 tract 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 "\nBridges 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 "\nBridges in third graph " g3.bridge()#This code is contributed by Neelam Yadav

// 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 tract 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 aadjacent 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

输出如下：

Bridges in first graph 3 4 0 3Bridges in second graph 2 3 1 2 0 1Bridges in third graph 1 6

时间复杂度：上面的功能是带有附加数组的简单DFS。因此, 时间复杂度与DFS相同, 对于图的邻接表表示, 它的时间复杂度为O(V + E)。
参考文献：
https://www.cs.washington.edu/education/courses/421/04su/slides/artic.pdf
Algorithm Design and Complexity - Course 8from Traian Rebedea
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L25-Connectivity.htm
【如何找到给定图(graph)中的所有桥（）】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。