Dado un gráfico no dirigido, imprima todos los componentes conectados línea por línea. Por ejemplo, considere el siguiente gráfico.
Hemos discutido algoritmos para encontrar componentes fuertemente conectados en gráficos dirigidos en las siguientes publicaciones.
Algoritmo de Kosaraju para componentes fuertemente conectados .
Algoritmo de Tarjan para encontrar componentes fuertemente conectados
Encontrar componentes conectados para un gráfico no dirigido es una tarea más fácil. Simplemente necesitamos hacer BFS o DFS comenzando desde cada vértice no visitado, y obtenemos todos los componentes fuertemente conectados. A continuación se muestran los pasos basados en DFS.
1) Initialize all vertices as not visited.
2) Do following for every vertex 'v'.
(a) If 'v' is not visited before, call DFSUtil(v)
(b) Print new line character
DFSUtil(v)
1) Mark 'v' as visited.
2) Print 'v'
3) Do following for every adjacent 'u' of 'v'.
If 'u' is not visited, then recursively call DFSUtil(u)
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to print connected components in
// an undirected graph
#include <iostream>
#include <list>
using namespace std;
// Graph class represents a undirected graph
// using adjacency list representation
class Graph {
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int>* adj;
// A function used by DFS
void DFSUtil(int v, bool visited[]);
public:
Graph(int V); // Constructor
~Graph();
void addEdge(int v, int w);
void connectedComponents();
};
// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
// Mark all the vertices as not visited
bool* visited = new bool[V];
for (int v = 0; v < V; v++)
visited[v] = false;
for (int v = 0; v < V; v++) {
if (visited[v] == false) {
// print all reachable vertices
// from v
DFSUtil(v, visited);
cout << "\n";
}
}
delete[] visited;
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
Graph::~Graph() { delete[] adj; }
// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
// Driver code
int main()
{
// Create a graph given in the above diagram
Graph g(5); // 5 vertices numbered from 0 to 4
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Following are connected components \n";
g.connectedComponents();
return 0;
}
Java
// Java program to print connected components in
// an undirected graph
import java.util.ArrayList;
class Graph
{
// A user define class to represent a graph.
// A graph is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
int V;
ArrayList<ArrayList<Integer> > adjListArray;
// constructor
Graph(int V)
{
this.V = V;
// define the size of array as
// number of vertices
adjListArray = new ArrayList<>();
// Create a new list for each vertex
// such that adjacent nodes can be stored
for (int i = 0; i < V; i++) {
adjListArray.add(i, new ArrayList<>());
}
}
// Adds an edge to an undirected graph
void addEdge(int src, int dest)
{
// Add an edge from src to dest.
adjListArray.get(src).add(dest);
// Since graph is undirected, add an edge from dest
// to src also
adjListArray.get(dest).add(src);
}
void DFSUtil(int v, boolean[] visited)
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v + " ");
// Recur for all the vertices
// adjacent to this vertex
for (int x : adjListArray.get(v)) {
if (!visited[x])
DFSUtil(x, visited);
}
}
void connectedComponents()
{
// Mark all the vertices as not visited
boolean[] visited = new boolean[V];
for (int v = 0; v < V; ++v) {
if (!visited[v]) {
// print all reachable vertices
// from v
DFSUtil(v, visited);
System.out.println();
}
}
}
// Driver code
public static void main(String[] args)
{
// Create a graph given in the above diagram
Graph g = new Graph(
5); // 5 vertices numbered from 0 to 4
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
System.out.println(
"Following are connected components");
g.connectedComponents();
}
}
Python3
# Python program to print connected
# components in an undirected graph
class Graph:
# init function to declare class variables
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
def DFSUtil(self, temp, v, visited):
# Mark the current vertex as visited
visited[v] = True
# Store the vertex to list
temp.append(v)
# Repeat for all vertices adjacent
# to this vertex v
for i in self.adj[v]:
if visited[i] == False:
# Update the list
temp = self.DFSUtil(temp, i, visited)
return temp
# method to add an undirected edge
def addEdge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
# Method to retrieve connected components
# in an undirected graph
def connectedComponents(self):
visited = []
cc = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
cc.append(self.DFSUtil(temp, v, visited))
return cc
# Driver Code
if __name__ == "__main__":
# Create a graph given in the above diagram
# 5 vertices numbered from 0 to 4
g = Graph(5)
g.addEdge(1, 0)
g.addEdge(2, 3)
g.addEdge(3, 4)
cc = g.connectedComponents()
print("Following are connected components")
print(cc)
# This code is contributed by Abhishek Valsan
C#
// C++ program to print connected components in
// an undirected graph
#include <iostream>
#include <list>
using namespace std;
// Graph class represents a undirected graph
// using adjacency list representation
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int>* adj;
// A function used by DFS
void DFSUtil(int v, bool visited[]);
public : Graph(int V); // Constructor
~Graph();
void addEdge(int v, int w);
void connectedComponents();
};
// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
// Mark all the vertices as not visited
bool* visited = new bool[V];
for (int v = 0; v < V; v++)
visited[v] = false;
for (int v = 0; v < V; v++) {
if (visited[v] == false) {
// print all reachable vertices
// from v
DFSUtil(v, visited);
cout << "\n";
}
}
delete[] visited;
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph::Graph(int V)
{
this -> V = V;
adj = new list<int>[ V ];
}
Graph::~Graph() { delete[] adj; }
// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
// Driver code
int main()
{
// Create a graph given in the above diagram
Graph g(5); // 5 vertices numbered from 0 to 4
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Following are connected components \n";
g.connectedComponents();
return 0;
}
Javascript
<script>
// Javascript program to print connected components in
// an undirected graph
// A user define class to represent a graph.
// A graph is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
let V;
let adjListArray=[];
// constructor
function Graph(v)
{
V = v
// define the size of array as
// number of vertices
// Create a new list for each vertex
// such that adjacent nodes can be stored
for (let i = 0; i < V; i++) {
adjListArray.push([]);
}
}
// Adds an edge to an undirected graph
function addEdge(src,dest)
{
// Add an edge from src to dest.
adjListArray[src].push(dest);
// Since graph is undirected, add an edge from dest
// to src also
adjListArray[dest].push(src);
}
function DFSUtil(v,visited)
{
// Mark the current node as visited and print it
visited[v] = true;
document.write(v + " ");
// Recur for all the vertices
// adjacent to this vertex
for (let x = 0; x < adjListArray[v].length; x++)
{
if (!visited[adjListArray[v][x]])
DFSUtil(adjListArray[v][x], visited);
}
}
function connectedComponents()
{
// Mark all the vertices as not visited
let visited = new Array(V);
for(let i = 0; i < V; i++)
{
visited[i] = false;
}
for (let v = 0; v < V; ++v)
{
if (!visited[v])
{
// print all reachable vertices
// from v
DFSUtil(v, visited);
document.write("<br>");
}
}
}
// Driver code
Graph(5);
addEdge(1, 0);
addEdge(2, 3);
addEdge(3, 4);
document.write(
"Following are connected components<br>");
connectedComponents();
// This code is contributed by rag2127
</script>
Producción
Following are connected components 0 1 2 3 4
La complejidad del tiempo de la solución anterior es O (V + E) ya que lo hace DFS simple para el gráfico dado.
Esto se puede resolver usando Disjoint Set Union con una complejidad de tiempo de O(N). La solución DSU es más fácil de entender e implementar.
Algoritmo:
- Declare una array arr de tamaño n donde n es el número total de Nodes.
- Para cada índice i de la array arr, el valor indica quién es el padre del i-ésimo vértice. Por ejemplo, es arr[0]=3, entonces podemos decir que el padre del vértice 0 es 3.
- Inicialice cada Node como el padre de sí mismo y luego, mientras los agrega, cambie sus padres en consecuencia.
C++
#include <bits/stdc++.h>
using namespace std;
int merge(int* parent, int x)
{
if (parent[x] == x)
return x;
return merge(parent, parent[x]);
}
int connectedcomponents(int n, vector<vector<int> >& edges)
{
int parent[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (auto x : edges) {
parent[merge(parent, x[0])] = merge(parent, x[1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (parent[i] == i);
}
for (int i = 0; i < n; i++) {
parent[i] = merge(parent, parent[i]);
}
map<int, list<int> > m;
for (int i = 0; i < n; i++) {
m[parent[i]].push_back(i);
}
for (auto it = m.begin(); it != m.end(); it++) {
list<int> l = it->second;
for (auto x : l) {
cout << x << " ";
}
cout << endl;
}
return ans;
}
int main()
{
int n = 5;
vector<int> e1 = { 0, 1 };
vector<int> e2 = { 2, 3 };
vector<int> e3 = { 3, 4 };
vector<vector<int> > e;
e.push_back(e1);
e.push_back(e2);
e.push_back(e3);
int a = connectedcomponents(n, e);
cout << "total no. of connected components are: " << a
<< endl;
return 0;
}
Producción
0 1 2 3 4 total no. of connected components are: 2
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