如何找到给定图(graph)中的所有桥?

2021年3月23日14:17:48 发表评论 969 次浏览

本文概述

无向连通图中的一条边是断开该图的桥。对于一个断开的无向图,它的定义是类似的,桥是一个删除边缘,增加断开组件的数量。

像连接点一样,桥表示连接网络中的漏洞,对于设计可靠的网络非常有用。例如,在有线计算机网络中,一个连接点表示关键计算机,一个桥表示关键导线或连接。

以下是一些带有红色突出显示的桥的示例图。

桥1
桥2
桥3

如何找到给定图中的所有桥?

一种简单的方法是一个接一个地删除所有边, 并查看是否删除边会导致图形断开。以下是连接图的简单方法步骤。

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 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 << "\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
  
     // Array  of 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

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 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 3

Bridges in second graph
2 3
1 2
0 1

Bridges in third graph
1 6

时间复杂度:上面的功能是带有附加数组的简单DFS。因此, 时间复杂度与DFS相同, 对于图的邻接表表示, 它的时间复杂度为O(V + E)。

参考文献:

https://www.cs.washington.edu/education/courses/421/04su/slides/artic.pdf

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L25-Connectivity.htm

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: