Dado un grafo no dirigido G , con V vértices y E aristas, la tarea es comprobar si el grafo tiene 2 aristas conectadas o no. Se dice que un grafo tiene 2 aristas conectadas si, al eliminar cualquier arista del gráfico, aún permanece conectado, es decir, no contiene puentes .
Ejemplos:
Entrada: V = 7, E = 9
Salida: Sí
Explicación:
Dado cualquier vértice en el gráfico, podemos llegar a cualquier otro vértice en el gráfico. Además, eliminar cualquier borde del gráfico no afecta su conectividad. Entonces, se dice que el gráfico está conectado por 2 aristas.Entrada: V = 8, E = 9
ejemplo2
Salida: No
Explicación:
Al eliminar el borde entre el vértice 3 y el vértice 4, el gráfico ya no está conectado. Entonces, el gráfico no está conectado por 2 aristas.
Enfoque ingenuo: el enfoque ingenuo es verificar que al eliminar cualquier borde X , si el gráfico restante G – X está conectado o no. Si el gráfico permanece conectado al eliminar cada borde uno por uno, entonces es un gráfico conectado de 2 bordes. Para implementar la idea anterior, elimine un borde y realice la búsqueda primero en profundidad (DFS) o la búsqueda primero en amplitud (BFS) desde cualquier vértice y verifique si todos los vértices están cubiertos o no. Repita este proceso para todos los bordes E. Si no se pueden atravesar todos los vértices para ningún borde, imprima No . De lo contrario, imprima Sí .
Complejidad de Tiempo: O(E * ( V + E))
Espacio Auxiliar: O(1)
Enfoque Eficiente: La idea para resolver este problema es:
Puentes en un gráfico: un borde en un gráfico conectado no dirigido es un puente si al quitarlo se desconecta el gráfico. Para un gráfico no dirigido desconectado, la definición es similar, un puente es una eliminación de bordes que aumenta el número de componentes desconectados.
=> Si hay algún puente en el gráfico, entonces nunca será una conexión de 2 aristas; de lo contrario, será una conexión de 2 aristas.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ program to find bridges in a given undirected graph
#include <bits/stdc++.h>
#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:
int count = 0;
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])
count++;
}
// 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 Code
int main()
{
Graph g1(6);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 0);
g1.addEdge(1, 3);
g1.addEdge(3, 4);
g1.addEdge(4, 5);
g1.addEdge(5, 3);
g1.bridge();
if (g1.count == 0) {
cout << "Given graph is 2-edge connected";
}
else {
cout << "Given graph is not 2-edge connected";
}
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;
static int count = 0;
// 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])
count++;
}
// 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(6);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 0);
g1.addEdge(1, 3);
g1.addEdge(3, 4);
g1.addEdge(4, 5);
g1.addEdge(5, 3);
g1.bridge();
if (g1.count == 0) {
System.out.println(
"Given graph is 2-edge connected:");
}
else {
System.out.println(
"Given graph is not 2-edge connected:");
}
}
}
// 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:
count = 0
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
# count = 0
# 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]:
self.count += 1
# Update low value of u for parent function calls.
elif v != parent[u]:
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(6)
g1.addEdge(0, 1)
g1.addEdge(1, 2)
g1.addEdge(2, 0)
g1.addEdge(1, 3)
g1.addEdge(3, 4)
g1.addEdge(4, 5)
g1.addEdge(5, 3)
g1.bridge()
if g1.count == 0:
print("Given graph is 2-edge connected")
else:
print("Given graph is not 2-edge connected")
# This code is contributed by Neelam Yadav
Producción
Given graph is not 2-edge connected
Complejidad Temporal: O(V + E)
Espacio Auxiliar: O(V)