Gráfico débilmente conectado:
Un grafo dirigido ‘ G = (V, E)’ es débilmente conexo si el grafo no dirigido subyacente Ĝ es conexo.
El gráfico no dirigido subyacente es el gráfico Ĝ = (V, Ê) donde Ê representa el conjunto de aristas no dirigidas que se obtiene quitando las puntas de flecha de las aristas dirigidas y haciéndolas bidireccionales en G .
Ejemplo:
El grafo dirigido G anterior es débilmente conexo ya que su grafo no dirigido subyacente Ĝ es conexo.
Componente débilmente conectado:
Dado un grafo dirigido, un componente débilmente conectado (WCC) es un subgrafo del grafo original donde todos los vértices están conectados entre sí por algún camino, ignorando la dirección de los bordes.
Ejemplo:
En el gráfico dirigido anterior, hay dos componentes débilmente conectados:
- [0, 1, 2, 3]
- [4, 5]
Algoritmo para encontrar el componente débilmente conectado:
Utiliza el algoritmo para encontrar componentes conectados de un gráfico no dirigido.
- Construya el gráfico no dirigido subyacente del gráfico dirigido dado.
- Encuentre todos los componentes conectados del gráfico no dirigido.
- Las componentes conexas del grafo no dirigido serán las componentes débilmente conexas del grafo dirigido.
Implementación:
A continuación se muestra el código del componente débilmente conectado que toma un gráfico dirigido DG como entrada y devuelve todos los componentes débilmente conectados WCC del gráfico de entrada.
Java
// Java Code for the above algorithm
import java.util.ArrayList;
class Graph {
int vertices;
ArrayList<ArrayList<Integer> > adjacencyList;
public Graph(int vertices)
{
this.vertices = vertices;
adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < this.vertices; i++)
adjacencyList.add(new ArrayList<>());
}
public void addEdge(int u, int v)
{
// Use of noEdge(int, int)
// prevents duplication of edges
if (noEdge(u, v))
adjacencyList.get(u).add(v);
}
// Returns true if there does NOT exist
// any edge from u to v
boolean noEdge(int u, int v)
{
for (int destination : adjacencyList.get(u))
if (destination == v)
return false;
return true;
}
}
class WCC {
private final Graph directedGraph;
public WCC(Graph directedGraph)
{
this.directedGraph = directedGraph;
}
// Finds all the connected components
// of the given undirected graph
private ArrayList<ArrayList<Integer> >
connectedComponents(Graph undirectedGraph)
{
ArrayList<ArrayList<Integer> > connectedComponents
= new ArrayList<>();
boolean[] isVisited
= new boolean[undirectedGraph.vertices];
for (int i = 0; i < undirectedGraph.vertices; i++) {
if (!isVisited[i]) {
ArrayList<Integer> component
= new ArrayList<>();
findConnectedComponent(i, isVisited,
component,
undirectedGraph);
connectedComponents.add(component);
}
}
return connectedComponents;
}
// Finds a connected component
// starting from source using DFS
private void
findConnectedComponent(int src, boolean[] isVisited,
ArrayList<Integer> component,
Graph undirectedGraph)
{
isVisited[src] = true;
component.add(src);
for (int v :
undirectedGraph.adjacencyList.get(src))
if (!isVisited[v])
findConnectedComponent(v, isVisited,
component,
undirectedGraph);
}
public ArrayList<ArrayList<Integer> >
weaklyConnectedComponents()
{
// Step 1: Construct the
// underlying undirected graph
Graph undirectedGraph
= new Graph(directedGraph.vertices);
for (int u = 0; u < directedGraph.vertices; u++) {
for (int v :
directedGraph.adjacencyList.get(u)) {
undirectedGraph.addEdge(u, v);
undirectedGraph.addEdge(v, u);
}
}
// Step 2: Find the connected components
// of the undirected graph
return connectedComponents(undirectedGraph);
}
}
public class WCCDemo {
// Driver Code
public static void main(String[] args)
{
Graph directedGraph = new Graph(6);
directedGraph.addEdge(0, 1);
directedGraph.addEdge(0, 2);
directedGraph.addEdge(3, 1);
directedGraph.addEdge(3, 2);
directedGraph.addEdge(4, 5);
ArrayList<ArrayList<Integer> >
weaklyConnectedComponents
= new WCC(directedGraph)
.weaklyConnectedComponents();
int index = 1;
for (ArrayList<Integer> component :
weaklyConnectedComponents) {
System.out.print("Component "
+ index++ + ": ");
for (Integer i : component)
System.out.print(i + " ");
System.out.println();
}
}
}
Component 1: 0 1 3 2 Component 2: 4 5
Complejidad temporal: O(V+E)
Publicación traducida automáticamente
Artículo escrito por anujanonymous y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA