En la publicación anterior , presentamos el algoritmo de búsqueda de unión y lo usamos para detectar el ciclo en un gráfico. Usamos las siguientes operaciones union() y find() para subconjuntos.
C++
// Naive implementation of find
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// Naive implementation of union()
void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
Java
// Naive implementation of find
static int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// Naive implementation of union()
static void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
// This code is contributed by divyesh072019
Python3
# Naive implementation of find def find(parent, i): if (parent[i] == -1): return i return find(parent, parent[i]) # Naive implementation of union() def Union(parent, x, y): xset = find(parent, x) yset = find(parent, y) parent[xset] = yset # This code is contributed by rutvik_56
C#
// Naive implementation of find
static int find(int []parent, int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// Naive implementation of union()
static void Union(int []parent, int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
// This code is contributed by pratham76
Javascript
<script>
// Naive implementation of find
function find(parent, i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// Naive implementation of union()
function Union(parent, x, y)
{
let xset = find(parent, x);
let yset = find(parent, y);
parent[xset] = yset;
}
<script>
Los anteriores union() y find() son ingenuos y, en el peor de los casos, la complejidad del tiempo es lineal. Los árboles creados para representar subconjuntos pueden estar sesgados y convertirse en una lista enlazada. A continuación se muestra un ejemplo del peor de los casos.
Let there be 4 elements 0, 1, 2, 3
Initially, all elements are single element subsets.
0 1 2 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
2 3
/
1
/
0
Do Union(2, 3)
3
/
2
/
1
/
0
Las operaciones anteriores se pueden optimizar a O (Log n) en el peor de los casos. La idea es colocar siempre un árbol de menor profundidad debajo de la raíz del árbol más profundo. Esta técnica se llama unión por rango . Se prefiere el término rango en lugar de altura porque si se usa la técnica de compresión de caminos (la discutimos más adelante), entonces el rango no siempre es igual a la altura. Además, el tamaño (en lugar de la altura) de los árboles también se puede usar como rango . El uso del tamaño como rango también produce una complejidad de tiempo en el peor de los casos como O (Iniciar sesión).
Let us see the above example with union by rank
Initially, all elements are single element subsets.
0 1 2 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
1 3
/ \
0 2
Do Union(2, 3)
1
/ | \
0 2 3
La segunda optimización del método ingenuo es Path Compression . La idea es aplanar el árbol cuando se llama a find() . Cuando se llama a find() para un elemento x, se devuelve la raíz del árbol. La operación find() atraviesa desde x para encontrar la raíz. La idea de la compresión de ruta es hacer que la raíz encontrada sea el padre de x para que no tengamos que atravesar todos los Nodes intermedios nuevamente. Si x es la raíz de un subárbol, entonces la ruta (a la raíz) desde todos los Nodes debajo de x también se comprime.
Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
9
/ | \
4 5 6
/ / \
0 7 8
/
3
/ \
1 2
When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 and 0 as the child of 9 so
that when find() is called next time for 0, 1, 2 or 3, the path to root is reduced.
--------9-------
/ / / \ \
0 4 5 6 3
/ \ / \
7 8 1 2
Las dos técnicas se complementan. La complejidad temporal de cada operación se vuelve incluso menor que O(Logn). De hecho, la complejidad del tiempo amortizado se convierte efectivamente en una pequeña constante.
A continuación se muestra la implementación basada en la compresión de unión por rango y ruta para encontrar un ciclo en un gráfico.
C++
// A C++ program to detect cycle in a graph using union by
// rank and path compression
#include <bits/stdc++.h>
using namespace std;
// a structure to represent an edge in the graph
struct Edge {
int src, dest;
};
// a structure to represent a graph
struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges
struct Edge* edge;
};
struct subset {
int parent;
int rank;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));
return graph;
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
// find root and make root as parent of i (path
// compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(struct subset subsets[], int xroot, int yroot)
{
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and
// increment its rank by one
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to check whether a given graph contains
// cycle or not
int isCycle(struct Graph* graph)
{
int V = graph->V;
int E = graph->E;
// Allocate memory for creating V sets
struct subset* subsets
= (struct subset*)malloc(V * sizeof(struct subset));
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Iterate through all edges of graph, find sets of both
// vertices of every edge, if sets are same, then there
// is cycle in graph.
for (int e = 0; e < E; ++e) {
int x = find(subsets, graph->edge[e].src);
int y = find(subsets, graph->edge[e].dest);
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
// Driver code
int main()
{
/* Let us create the following graph
0
| \
| \
1-----2 */
int V = 3, E = 3;
struct Graph* graph = createGraph(V, E);
// add edge 0-1
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
// add edge 1-2
graph->edge[1].src = 1;
graph->edge[1].dest = 2;
// add edge 0-2
graph->edge[2].src = 0;
graph->edge[2].dest = 2;
if (isCycle(graph))
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// A C program to detect cycle in a graph using union by
// rank and path compression
#include <stdio.h>
#include <stdlib.h>
// a structure to represent an edge in the graph
typedef struct Edge {
int src, dest;
}Edge;
// a structure to represent a graph
typedef struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges
struct Edge* edge;
}Graph;
typedef struct subset {
int parent;
int rank;
}subset;
// Creates a graph with V vertices and E edges
Graph* createGraph(int V, int E)
{
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->E = E;
graph->edge = (Edge*)malloc(graph->E * sizeof(Edge));
return graph;
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(subset subsets[], int i)
{
// find root and make root as parent of i (path
// compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(subset subsets[], int xroot, int yroot)
{
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and
// increment its rank by one
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to check whether a given graph contains
// cycle or not
int isCycle(Graph* graph)
{
int V = graph->V;
int E = graph->E;
// Allocate memory for creating V sets
subset* subsets = (subset*)malloc(V * sizeof(subset));
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Iterate through all edges of graph, find sets of both
// vertices of every edge, if sets are same, then there
// is cycle in graph.
for (int e = 0; e < E; ++e) {
int x = find(subsets, graph->edge[e].src);
int y = find(subsets, graph->edge[e].dest);
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
// Driver code
int main()
{
/* Let us create the following graph
0
| \
| \
1-----2 */
int V = 3, E = 3;
Graph* graph = createGraph(V, E);
// add edge 0-1
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
// add edge 1-2
graph->edge[1].src = 1;
graph->edge[1].dest = 2;
// add edge 0-2
graph->edge[2].src = 0;
graph->edge[2].dest = 2;
if (isCycle(graph))
printf("Graph contains cycle");
else
printf("Graph doesn't contain cycle");
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// A union by rank and path compression
// based program to detect cycle in a graph
class Graph
{
int V, E;
Edge[] edge;
Graph(int nV, int nE)
{
V = nV;
E = nE;
edge = new Edge[E];
for (int i = 0; i < E; i++)
{
edge[i] = new Edge();
}
}
// class to represent edge
class Edge
{
int src, dest;
}
// class to represent Subset
class subset
{
int parent;
int rank;
}
// A utility function to find
// set of an element i (uses
// path compression technique)
int find(subset[] subsets, int i)
{
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union
// of two sets of x and y
// (uses union by rank)
void Union(subset[] subsets, int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[yroot].rank < subsets[xroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[xroot].parent = yroot;
subsets[yroot].rank++;
}
}
// The main function to check whether
// a given graph contains cycle or not
int isCycle(Graph graph)
{
int V = graph.V;
int E = graph.E;
subset[] subsets = new subset[V];
for (int v = 0; v < V; v++) {
subsets[v] = new subset();
subsets[v].parent = v;
subsets[v].rank = 0;
}
for (int e = 0; e < E; e++) {
int x = find(subsets, graph.edge[e].src);
int y = find(subsets, graph.edge[e].dest);
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
/* Let us create the following graph
0
| \
| \
1-----2 */
int V = 3, E = 3;
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
// add edge 1-2
graph.edge[1].src = 1;
graph.edge[1].dest = 2;
// add edge 0-2
graph.edge[2].src = 0;
graph.edge[2].dest = 2;
if (graph.isCycle(graph) == 1)
System.out.println("Graph contains cycle");
else
System.out.println(
"Graph doesn't contain cycle");
}
}
// This code is contributed
// by ashwani khemani
Python3
# A union by rank and path compression based
# program to detect cycle in a graph
from collections import defaultdict
# a structure to represent a graph
class Graph:
def __init__(self, num_of_v):
self.num_of_v = num_of_v
self.edges = defaultdict(list)
# graph is represented as an
# array of edges
def add_edge(self, u, v):
self.edges[u].append(v)
class Subset:
def __init__(self, parent, rank):
self.parent = parent
self.rank = rank
# A utility function to find set of an element
# node(uses path compression technique)
def find(subsets, node):
if subsets[node].parent != node:
subsets[node].parent = find(subsets, subsets[node].parent)
return subsets[node].parent
# A function that does union of two sets
# of u and v(uses union by rank)
def union(subsets, u, v):
# Attach smaller rank tree under root
# of high rank tree(Union by Rank)
if subsets[u].rank > subsets[v].rank:
subsets[v].parent = u
elif subsets[v].rank > subsets[u].rank:
subsets[u].parent = v
# If ranks are same, then make one as
# root and increment its rank by one
else:
subsets[v].parent = u
subsets[u].rank += 1
# The main function to check whether a given
# graph contains cycle or not
def isCycle(graph):
# Allocate memory for creating sets
subsets = []
for u in range(graph.num_of_v):
subsets.append(Subset(u, 0))
# Iterate through all edges of graph,
# find sets of both vertices of every
# edge, if sets are same, then there
# is cycle in graph.
for u in graph.edges:
u_rep = find(subsets, u)
for v in graph.edges[u]:
v_rep = find(subsets, v)
if u_rep == v_rep:
return True
else:
union(subsets, u_rep, v_rep)
# Driver Code
g = Graph(3)
# add edge 0-1
g.add_edge(0, 1)
# add edge 1-2
g.add_edge(1, 2)
# add edge 0-2
g.add_edge(0, 2)
if isCycle(g):
print('Graph contains cycle')
else:
print('Graph does not contain cycle')
# This code is contributed by
# Sampath Kumar Surine
C#
// A union by rank and path compression
// based program to detect cycle in a graph
using System;
class Graph {
public int V, E;
public Edge[] edge;
public Graph(int nV, int nE)
{
V = nV;
E = nE;
edge = new Edge[E];
for (int i = 0; i < E; i++)
{
edge[i] = new Edge();
}
}
// class to represent edge
public class Edge {
public int src, dest;
}
// class to represent Subset
class subset
{
public int parent;
public int rank;
}
// A utility function to find
// set of an element i (uses
// path compression technique)
int find(subset[] subsets, int i)
{
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union
// of two sets of x and y
// (uses union by rank)
void Union(subset[] subsets, int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[yroot].rank < subsets[xroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[xroot].parent = yroot;
subsets[yroot].rank++;
}
}
// The main function to check whether
// a given graph contains cycle or not
int isCycle(Graph graph)
{
int V = graph.V;
int E = graph.E;
subset[] subsets = new subset[V];
for (int v = 0; v < V; v++)
{
subsets[v] = new subset();
subsets[v].parent = v;
subsets[v].rank = 0;
}
for (int e = 0; e < E; e++)
{
int x = find(subsets, graph.edge[e].src);
int y = find(subsets, graph.edge[e].dest);
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
// Driver Code
static public void Main(String[] args)
{
/* Let us create the following graph
0
| \
| \
1-----2 */
int V = 3, E = 3;
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
// add edge 1-2
graph.edge[1].src = 1;
graph.edge[1].dest = 2;
// add edge 0-2
graph.edge[2].src = 0;
graph.edge[2].dest = 2;
if (graph.isCycle(graph) == 1)
Console.WriteLine("Graph contains cycle");
else
Console.WriteLine(
"Graph doesn't contain cycle");
}
}
// This code is contributed
// by Arnab Kundu
Javascript
<script>
// A union by rank and path compression
// based program to detect cycle in a graph
let V, E;
let edge;
function Graph(nV,nE)
{
V = nV;
E = nE;
edge = new Array(E);
for (let i = 0; i < E; i++)
{
edge[i] = new Edge();
}
}
// class to represent edge
class Edge
{
constructor()
{
this.src=0;
this.dest=0;
}
}
// class to represent Subset
class subset
{
constructor()
{
this.parent=0;
this.rank=0;
}
}
// A utility function to find
// set of an element i (uses
// path compression technique)
function find(subsets,i)
{
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union
// of two sets of x and y
// (uses union by rank)
function Union(subsets,x,y)
{
let xroot = find(subsets, x);
let yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[yroot].rank < subsets[xroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[xroot].parent = yroot;
subsets[yroot].rank++;
}
}
// The main function to check whether
// a given graph contains cycle or not
function isCycle()
{
let subsets = new Array(V);
for (let v = 0; v < V; v++) {
subsets[v] = new subset();
subsets[v].parent = v;
subsets[v].rank = 0;
}
for (let e = 0; e < E; e++) {
let x = find(subsets, edge[e].src);
let y = find(subsets, edge[e].dest);
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
// Driver Code
/* Let us create the following graph
0
| \
| \
1-----2 */
V = 3, E = 3;
Graph(V, E);
// add edge 0-1
edge[0].src = 0;
edge[0].dest = 1;
// add edge 1-2
edge[1].src = 1;
edge[1].dest = 2;
// add edge 0-2
edge[2].src = 0;
edge[2].dest = 2;
if (isCycle() == 1)
document.write("Graph contains cycle");
else
document.write(
"Graph doesn't contain cycle");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Graph contains cycle
Artículos relacionados :
- Algoritmo de búsqueda de unión | Conjunto 1 (Detectar ciclo en un gráfico no dirigido)
- Estructuras de datos de conjuntos disjuntos (Implementación de Java)
- Algoritmos codiciosos | Conjunto 2 (algoritmo de árbol de expansión mínimo de Kruskal)
- Problema de secuenciación de trabajos | Conjunto 2 (usando conjunto disjunto)
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