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

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

## 本文概述

1)对于每个边(u, v), 请执行以下操作

…..a)从图表中删除(u, v)

..…b)查看图形是否保持连接状态(我们可以使用BFS或DFS)

…..c)将(u, v)添加回图形。

O(V + E)算法查找所有桥梁

## 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
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[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;
{
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.bridge();

cout << "\nBridges in second graph \n" ;
Graph g2(4);
g2.bridge();

cout << "\nBridges in third graph \n" ;
Graph g3(7);
g3.bridge();

return 0;
}``````

## Java

``````// A Java program to find bridges in a given undirected graph
import java.io.*;
import java.util.*;

// 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
int time = 0 ;
static final int NIL = - 1 ;

// Constructor
Graph( int v)
{
V = v;
for ( int i= 0 ; i<v; ++i)
}

// Function to add an edge into the graph
void addEdge( int v, int w)
{
}

// 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
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.bridge();
System.out.println();

System.out.println( "Bridges in Second graph" );
Graph g2 = new Graph( 4 );
g2.bridge();
System.out.println();

System.out.println( "Bridges in Third graph " );
Graph g3 = new Graph( 7 );
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 )

print "Bridges in first graph "
g1.bridge()

g2 = Graph( 4 )
print "\nBridges in second graph "
g2.bridge()

g3 = Graph ( 7 )
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
public class Graph
{
private int V; // No. of vertices

// Array of lists for Adjacency List Representation
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)
{
}

// 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.bridge();
Console.WriteLine();

Console.WriteLine( "Bridges in Second graph" );
Graph g2 = new Graph(4);
g2.bridge();
Console.WriteLine();

Console.WriteLine( "Bridges in Third graph " );
Graph g3 = new Graph(7);
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``````

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 