Un componente biconexo es un subgrafo biconexo maximal .
El gráfico biconectado ya se trata aquí . En este artículo, veremos cómo encontrar el componente biconectado en un gráfico usando el algoritmo de John Hopcroft y Robert Tarjan.
En el gráfico anterior, los siguientes son los componentes biconectados:
- 4–2 3–4 3–1 2–3 1–2
- 8–9
- 8–5 7–8 5–7
- 6–0 5–6 1–5 0–1
- 10–11
El algoritmo se basa en el disco y los valores bajos discutidos en el artículo de componentes fuertemente conectados .
La idea es almacenar los bordes visitados en una pila mientras DFS en un gráfico y seguir buscando puntos de articulación (resaltados en la figura anterior). Tan pronto como se encuentra un punto de articulación u, todos los bordes visitados mientras DFS desde el Node u en adelante formarán un componente biconectado . Cuando DFS se completa para un componente conectado , todos los bordes presentes en la pila formarán un componente biconectado.
Si no hay un punto de articulación en el gráfico, entonces el gráfico está biconectado y, por lo tanto, habrá un componente biconectado que es el gráfico mismo.
C++
// A C++ program to find biconnected components in a given undirected graph
#include <iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
int count = 0;
class Edge {
public:
int u;
int v;
Edge(int u, int v);
};
Edge::Edge(int u, int v)
{
this->u = u;
this->v = v;
}
// A class that represents an directed graph
class Graph {
int V; // No. of vertices
int E; // No. of edges
list<int>* adj; // A dynamic array of adjacency lists
// A Recursive DFS based function used by BCC()
void BCCUtil(int u, int disc[], int low[],
list<Edge>* st, int parent[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BCC(); // prints strongly connected components
};
Graph::Graph(int V)
{
this->V = V;
this->E = 0;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
E++;
}
// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// *st -- >> To store visited edges
void Graph::BCCUtil(int u, int disc[], int low[], list<Edge>* st,
int parent[])
{
// A static variable is used for simplicity, we can avoid use
// of static variable by passing a pointer.
static int time = 0;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
int children = 0;
// 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 (disc[v] == -1) {
children++;
parent[v] = u;
// store the edge in stack
st->push_back(Edge(u, v));
BCCUtil(v, disc, low, st, parent);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
// Case 1 -- per Strongly Connected Components Article
low[u] = min(low[u], low[v]);
// If u is an articulation point,
// pop all edges from stack till u -- v
if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
while (st->back().u != u || st->back().v != v) {
cout << st->back().u << "--" << st->back().v << " ";
st->pop_back();
}
cout << st->back().u << "--" << st->back().v;
st->pop_back();
cout << endl;
count++;
}
}
// Update low value of 'u' only of 'v' is still in stack
// (i.e. it's a back edge, not cross edge).
// Case 2 -- per Strongly Connected Components Article
else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
if (disc[v] < disc[u]) {
st->push_back(Edge(u, v));
}
}
}
}
// The function to do DFS traversal. It uses BCCUtil()
void Graph::BCC()
{
int* disc = new int[V];
int* low = new int[V];
int* parent = new int[V];
list<Edge>* st = new list<Edge>[E];
// Initialize disc and low, and parent arrays
for (int i = 0; i < V; i++) {
disc[i] = NIL;
low[i] = NIL;
parent[i] = NIL;
}
for (int i = 0; i < V; i++) {
if (disc[i] == NIL)
BCCUtil(i, disc, low, st, parent);
int j = 0;
// If stack is not empty, pop all edges from stack
while (st->size() > 0) {
j = 1;
cout << st->back().u << "--" << st->back().v << " ";
st->pop_back();
}
if (j == 1) {
cout << endl;
count++;
}
}
}
// Driver program to test above function
int main()
{
Graph g(12);
g.addEdge(0, 1);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(3, 1);
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(2, 4);
g.addEdge(4, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(1, 5);
g.addEdge(5, 1);
g.addEdge(0, 6);
g.addEdge(6, 0);
g.addEdge(5, 6);
g.addEdge(6, 5);
g.addEdge(5, 7);
g.addEdge(7, 5);
g.addEdge(5, 8);
g.addEdge(8, 5);
g.addEdge(7, 8);
g.addEdge(8, 7);
g.addEdge(8, 9);
g.addEdge(9, 8);
g.addEdge(10, 11);
g.addEdge(11, 10);
g.BCC();
cout << "Above are " << count << " biconnected components in graph";
return 0;
}
Java
// A Java program to find biconnected components in a given
// undirected graph
import java.io.*;
import java.util.*;
// This class represents a directed graph using adjacency
// list representation
class Graph {
private int V, E; // No. of vertices & Edges respectively
private LinkedList<Integer> adj[]; // Adjacency List
// Count is number of biconnected components. time is
// used to find discovery times
static int count = 0, time = 0;
class Edge {
int u;
int v;
Edge(int u, int v)
{
this.u = u;
this.v = v;
}
};
// Constructor
Graph(int v)
{
V = v;
E = 0;
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);
E++;
}
// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// *st -- >> To store visited edges
void BCCUtil(int u, int disc[], int low[], LinkedList<Edge> st,
int parent[])
{
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
int children = 0;
// Go through all vertices adjacent to this
Iterator<Integer> it = adj[u].iterator();
while (it.hasNext()) {
int v = it.next(); // v is current adjacent of 'u'
// If v is not visited yet, then recur for it
if (disc[v] == -1) {
children++;
parent[v] = u;
// store the edge in stack
st.add(new Edge(u, v));
BCCUtil(v, disc, low, st, parent);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
// Case 1 -- per Strongly Connected Components Article
if (low[u] > low[v])
low[u] = low[v];
// If u is an articulation point,
// pop all edges from stack till u -- v
if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
while (st.getLast().u != u || st.getLast().v != v) {
System.out.print(st.getLast().u + "--" + st.getLast().v + " ");
st.removeLast();
}
System.out.println(st.getLast().u + "--" + st.getLast().v + " ");
st.removeLast();
count++;
}
}
// Update low value of 'u' only if 'v' is still in stack
// (i.e. it's a back edge, not cross edge).
// Case 2 -- per Strongly Connected Components Article
else if (v != parent[u] && disc[v] < disc[u] ) {
if (low[u] > disc[v])
low[u] = disc[v];
st.add(new Edge(u, v));
}
}
}
// The function to do DFS traversal. It uses BCCUtil()
void BCC()
{
int disc[] = new int[V];
int low[] = new int[V];
int parent[] = new int[V];
LinkedList<Edge> st = new LinkedList<Edge>();
// Initialize disc and low, and parent arrays
for (int i = 0; i < V; i++) {
disc[i] = -1;
low[i] = -1;
parent[i] = -1;
}
for (int i = 0; i < V; i++) {
if (disc[i] == -1)
BCCUtil(i, disc, low, st, parent);
int j = 0;
// If stack is not empty, pop all edges from stack
while (st.size() > 0) {
j = 1;
System.out.print(st.getLast().u + "--" + st.getLast().v + " ");
st.removeLast();
}
if (j == 1) {
System.out.println();
count++;
}
}
}
public static void main(String args[])
{
Graph g = new Graph(12);
g.addEdge(0, 1);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(3, 1);
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(2, 4);
g.addEdge(4, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(1, 5);
g.addEdge(5, 1);
g.addEdge(0, 6);
g.addEdge(6, 0);
g.addEdge(5, 6);
g.addEdge(6, 5);
g.addEdge(5, 7);
g.addEdge(7, 5);
g.addEdge(5, 8);
g.addEdge(8, 5);
g.addEdge(7, 8);
g.addEdge(8, 7);
g.addEdge(8, 9);
g.addEdge(9, 8);
g.addEdge(10, 11);
g.addEdge(11, 10);
g.BCC();
System.out.println("Above are " + g.count + " biconnected components in graph");
}
}
// This code is contributed by Aakash Hasija
Python3
# Python program to find biconnected components in a given
# undirected graph
# Complexity : O(V + E)
from collections import defaultdict
# This class represents an directed graph
# using adjacency list representation
class Graph:
def __init__(self, vertices):
# No. of vertices
self.V = vertices
# default dictionary to store graph
self.graph = defaultdict(list)
# time is used to find discovery times
self.Time = 0
# Count is number of biconnected components
self.count = 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 strongly connected
components using DFS traversal
u --> The vertex to be visited next
disc[] --> Stores discovery times of visited vertices
low[] -- >> earliest visited vertex (the vertex with minimum
discovery time) that can be reached from subtree
rooted with current vertex
st -- >> To store visited edges'''
def BCCUtil(self, u, parent, low, disc, st):
# Count of children in current node
children = 0
# 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 disc[v] == -1 :
parent[v] = u
children += 1
st.append((u, v)) # store the edge in stack
self.BCCUtil(v, parent, low, disc, st)
# Check if the subtree rooted with v has a connection to
# one of the ancestors of u
# Case 1 -- per Strongly Connected Components Article
low[u] = min(low[u], low[v])
# If u is an articulation point, pop
# all edges from stack till (u, v)
if parent[u] == -1 and children > 1 or parent[u] != -1 and low[v] >= disc[u]:
self.count += 1 # increment count
w = -1
while w != (u, v):
w = st.pop()
print(w,end=" ")
print()
elif v != parent[u] and low[u] > disc[v]:
'''Update low value of 'u' only of 'v' is still in stack
(i.e. it's a back edge, not cross edge).
Case 2
-- per Strongly Connected Components Article'''
low[u] = min(low [u], disc[v])
st.append((u, v))
# The function to do DFS traversal.
# It uses recursive BCCUtil()
def BCC(self):
# Initialize disc and low, and parent arrays
disc = [-1] * (self.V)
low = [-1] * (self.V)
parent = [-1] * (self.V)
st = []
# Call the recursive helper function to
# find articulation points
# in DFS tree rooted with vertex 'i'
for i in range(self.V):
if disc[i] == -1:
self.BCCUtil(i, parent, low, disc, st)
# If stack is not empty, pop all edges from stack
if st:
self.count = self.count + 1
while st:
w = st.pop()
print(w,end=" ")
print ()
# Create a graph given in the above diagram
g = Graph(12)
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(2, 3)
g.addEdge(2, 4)
g.addEdge(3, 4)
g.addEdge(1, 5)
g.addEdge(0, 6)
g.addEdge(5, 6)
g.addEdge(5, 7)
g.addEdge(5, 8)
g.addEdge(7, 8)
g.addEdge(8, 9)
g.addEdge(10, 11)
g.BCC();
print ("Above are % d biconnected components in graph" %(g.count));
# This code is contributed by Neelam Yadav
C#
// A C# program to find biconnected components in a given
// undirected graph
using System;
using System.Collections.Generic;
// This class represents a directed graph using adjacency
// list representation
public class Graph
{
private int V, E; // No. of vertices & Edges respectively
private List<int> []adj; // Adjacency List
// Count is number of biconnected components. time is
// used to find discovery times
int count = 0, time = 0;
class Edge
{
public int u;
public int v;
public Edge(int u, int v)
{
this.u = u;
this.v = v;
}
};
// Constructor
public Graph(int v)
{
V = v;
E = 0;
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);
E++;
}
// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// *st -- >> To store visited edges
void BCCUtil(int u, int []disc, int []low, List<Edge> st,
int []parent)
{
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
int children = 0;
// Go through all vertices adjacent to this
foreach(int it in adj[u])
{
int v = it; // v is current adjacent of 'u'
// If v is not visited yet, then recur for it
if (disc[v] == -1)
{
children++;
parent[v] = u;
// store the edge in stack
st.Add(new Edge(u, v));
BCCUtil(v, disc, low, st, parent);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
// Case 1 -- per Strongly Connected Components Article
if (low[u] > low[v])
low[u] = low[v];
// If u is an articulation point,
// pop all edges from stack till u -- v
if ((disc[u] == 1 && children > 1) ||
(disc[u] > 1 && low[v] >= disc[u]))
{
while (st[st.Count-1].u != u ||
st[st.Count-1].v != v)
{
Console.Write(st[st.Count - 1].u + "--" +
st[st.Count - 1].v + " ");
st.RemoveAt(st.Count - 1);
}
Console.WriteLine(st[st.Count - 1].u + "--" +
st[st.Count - 1].v + " ");
st.RemoveAt(st.Count - 1);
count++;
}
}
// Update low value of 'u' only if 'v' is still in stack
// (i.e. it's a back edge, not cross edge).
// Case 2 -- per Strongly Connected Components Article
else if (v != parent[u] && disc[v] < disc[u] )
{
if (low[u] > disc[v])
low[u] = disc[v];
st.Add(new Edge(u, v));
}
}
}
// The function to do DFS traversal. It uses BCCUtil()
void BCC()
{
int []disc = new int[V];
int []low = new int[V];
int []parent = new int[V];
List<Edge> st = new List<Edge>();
// Initialize disc and low, and parent arrays
for (int i = 0; i < V; i++)
{
disc[i] = -1;
low[i] = -1;
parent[i] = -1;
}
for (int i = 0; i < V; i++)
{
if (disc[i] == -1)
BCCUtil(i, disc, low, st, parent);
int j = 0;
// If stack is not empty, pop all edges from stack
while (st.Count > 0)
{
j = 1;
Console.Write(st[st.Count - 1].u + "--" +
st[st.Count - 1].v + " ");
st.RemoveAt(st.Count - 1);
}
if (j == 1)
{
Console.WriteLine();
count++;
}
}
}
// Driver code
public static void Main(String []args)
{
Graph g = new Graph(12);
g.addEdge(0, 1);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(3, 1);
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(2, 4);
g.addEdge(4, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(1, 5);
g.addEdge(5, 1);
g.addEdge(0, 6);
g.addEdge(6, 0);
g.addEdge(5, 6);
g.addEdge(6, 5);
g.addEdge(5, 7);
g.addEdge(7, 5);
g.addEdge(5, 8);
g.addEdge(8, 5);
g.addEdge(7, 8);
g.addEdge(8, 7);
g.addEdge(8, 9);
g.addEdge(9, 8);
g.addEdge(10, 11);
g.addEdge(11, 10);
g.BCC();
Console.WriteLine("Above are " + g.count +
" biconnected components in graph");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// A Javascript program to find biconnected components in a given
// undirected graph
class Edge
{
constructor(u,v)
{
this.u = u;
this.v = v;
}
}
// This class represents a directed graph using adjacency
// list representation
class Graph
{
// Constructor
constructor(v)
{
this.count=0;
this.time = 0;
this.V = v;
this.E = 0;
this.adj = new Array(v);
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);
this.E++;
}
// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// *st -- >> To store visited edges
BCCUtil(u,disc,low,st,parent)
{
// Initialize discovery time and low value
disc[u] = low[u] = ++this.time;
let children = 0;
// Go through all vertices adjacent to this
for(let it of this.adj[u].values()) {
let v = it; // v is current adjacent of 'u'
// If v is not visited yet, then recur for it
if (disc[v] == -1) {
children++;
parent[v] = u;
// store the edge in stack
st.push(new Edge(u, v));
this.BCCUtil(v, disc, low, st, parent);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
// Case 1 -- per Strongly Connected Components Article
if (low[u] > low[v])
low[u] = low[v];
// If u is an articulation point,
// pop all edges from stack till u -- v
if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
while (st[st.length-1].u != u || st[st.length-1].v != v) {
document.write(st[st.length-1].u + "--" + st[st.length-1].v + " ");
st.pop();
}
document.write(st[st.length-1].u + "--" + st[st.length-1].v + " <br>");
st.pop();
this.count++;
}
}
// Update low value of 'u' only if 'v' is still in stack
// (i.e. it's a back edge, not cross edge).
// Case 2 -- per Strongly Connected Components Article
else if (v != parent[u] && disc[v] < disc[u] ) {
if (low[u] > disc[v])
low[u] = disc[v];
st.push(new Edge(u, v));
}
}
}
// The function to do DFS traversal. It uses BCCUtil()
BCC()
{
let disc = new Array(this.V);
let low = new Array(this.V);
let parent = new Array(this.V);
let st = [];
// Initialize disc and low, and parent arrays
for (let i = 0; i < this.V; i++) {
disc[i] = -1;
low[i] = -1;
parent[i] = -1;
}
for (let i = 0; i < this.V; i++) {
if (disc[i] == -1)
this.BCCUtil(i, disc, low, st, parent);
let j = 0;
// If stack is not empty, pop all edges from stack
while (st.length > 0) {
j = 1;
document.write(st[st.length-1].u + "--" + st[st.length-1].v + " ");
st.pop();
}
if (j == 1) {
document.write("<br>");
this.count++;
}
}
}
}
let g = new Graph(12);
g.addEdge(0, 1);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(3, 1);
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(2, 4);
g.addEdge(4, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(1, 5);
g.addEdge(5, 1);
g.addEdge(0, 6);
g.addEdge(6, 0);
g.addEdge(5, 6);
g.addEdge(6, 5);
g.addEdge(5, 7);
g.addEdge(7, 5);
g.addEdge(5, 8);
g.addEdge(8, 5);
g.addEdge(7, 8);
g.addEdge(8, 7);
g.addEdge(8, 9);
g.addEdge(9, 8);
g.addEdge(10, 11);
g.addEdge(11, 10);
g.BCC();
document.write("Above are " + g.count + " biconnected components in graph");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
4--2 3--4 3--1 2--3 1--2 8--9 8--5 7--8 5--7 6--0 5--6 1--5 0--1 10--11 Above are 5 biconnected components in graph
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA