Dado un grafo no dirigido, imprime todos los vértices que forman ciclos en él.
Requisito previo: Detectar ciclo en un gráfico dirigido usando colores
En el diagrama anterior, los ciclos se han marcado con color verde oscuro. La salida para lo anterior será
1er ciclo: 3 5 4 6
2do ciclo: 11 12 13
Planteamiento: Usando el método de coloreado de gráficos , marca todos los vértices de los diferentes ciclos con números únicos. Una vez que se completa el recorrido del gráfico, empuje todos los números marcados similares a una lista de adyacencia e imprima la lista de adyacencia en consecuencia. A continuación se muestra el algoritmo:
- Inserte los bordes en una lista de adyacencia.
- Llame a la función DFS que utiliza el método de coloreado para marcar el vértice.
- Siempre que haya un vértice visitado parcialmente, retroceda hasta alcanzar el vértice actual y márquelos todos con números de ciclo. Una vez que todos los vértices estén marcados, aumente el número de ciclo.
- Una vez que se completa Dfs, repita los bordes y empuje los mismos bordes de números marcados a otra lista de adyacencia.
- Iterar en otra lista de adyacencia e imprimir el número de ciclo del vértice.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all the cycles
// in an undirected graph
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
// variables to be used
// in both functions
vector<int> graph[N];
vector<int> cycles[N];
// Function to mark the vertex with
// different colors for different cycles
void dfs_cycle(int u, int p, int color[],
int mark[], int par[], int& cyclenumber)
{
// already (completely) visited vertex.
if (color[u] == 2) {
return;
}
// seen vertex, but was not completely visited -> cycle detected.
// backtrack based on parents to find the complete cycle.
if (color[u] == 1) {
cyclenumber++;
int cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which are
// in the current cycle thats found
while (cur != u) {
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
for (int v : graph[u]) {
// if it has not been visited previously
if (v == par[u]) {
continue;
}
dfs_cycle(v, u, color, mark, par, cyclenumber);
}
// completely visited.
color[u] = 2;
}
// add the edges to the graph
void addEdge(int u, int v)
{
graph[u].push_back(v);
graph[v].push_back(u);
}
// Function to print the cycles
void printCycles(int edges, int mark[], int& cyclenumber)
{
// push the edges that into the
// cycle adjacency list
for (int i = 1; i <= edges; i++) {
if (mark[i] != 0)
cycles[mark[i]].push_back(i);
}
// print all the vertex with same cycle
for (int i = 1; i <= cyclenumber; i++) {
// Print the i-th cycle
cout << "Cycle Number " << i << ": ";
for (int x : cycles[i])
cout << x << " ";
cout << endl;
}
}
// Driver Code
int main()
{
// add edges
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 4);
addEdge(4, 6);
addEdge(4, 7);
addEdge(5, 6);
addEdge(3, 5);
addEdge(7, 8);
addEdge(6, 10);
addEdge(5, 9);
addEdge(10, 11);
addEdge(11, 12);
addEdge(11, 13);
addEdge(12, 13);
// arrays required to color the
// graph, store the parent of node
int color[N];
int par[N];
// mark with unique numbers
int mark[N];
// store the numbers of cycle
int cyclenumber = 0;
int edges = 13;
// call DFS to mark the cycles
dfs_cycle(1, 0, color, mark, par, cyclenumber);
// function to print the cycles
printCycles(edges, mark, cyclenumber);
}
Java
// Java program to print all the cycles
// in an undirected graph
import java.util.*;
class GFG
{
static final int N = 100000;
// variables to be used
// in both functions
@SuppressWarnings("unchecked")
static Vector<Integer>[] graph = new Vector[N];
@SuppressWarnings("unchecked")
static Vector<Integer>[] cycles = new Vector[N];
static int cyclenumber;
// Function to mark the vertex with
// different colors for different cycles
static void dfs_cycle(int u, int p, int[] color,
int[] mark, int[] par)
{
// already (completely) visited vertex.
if (color[u] == 2)
{
return;
}
// seen vertex, but was not completely visited -> cycle detected.
// backtrack based on parents to find the complete cycle.
if (color[u] == 1)
{
cyclenumber++;
int cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which are
// in the current cycle thats found
while (cur != u)
{
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
for (int v : graph[u])
{
// if it has not been visited previously
if (v == par[u])
{
continue;
}
dfs_cycle(v, u, color, mark, par);
}
// completely visited.
color[u] = 2;
}
// add the edges to the graph
static void addEdge(int u, int v)
{
graph[u].add(v);
graph[v].add(u);
}
// Function to print the cycles
static void printCycles(int edges, int mark[])
{
// push the edges that into the
// cycle adjacency list
for (int i = 1; i <= edges; i++)
{
if (mark[i] != 0)
cycles[mark[i]].add(i);
}
// print all the vertex with same cycle
for (int i = 1; i <= cyclenumber; i++)
{
// Print the i-th cycle
System.out.printf("Cycle Number %d: ", i);
for (int x : cycles[i])
System.out.printf("%d ", x);
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
for (int i = 0; i < N; i++)
{
graph[i] = new Vector<>();
cycles[i] = new Vector<>();
}
// add edges
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 4);
addEdge(4, 6);
addEdge(4, 7);
addEdge(5, 6);
addEdge(3, 5);
addEdge(7, 8);
addEdge(6, 10);
addEdge(5, 9);
addEdge(10, 11);
addEdge(11, 12);
addEdge(11, 13);
addEdge(12, 13);
// arrays required to color the
// graph, store the parent of node
int[] color = new int[N];
int[] par = new int[N];
// mark with unique numbers
int[] mark = new int[N];
// store the numbers of cycle
cyclenumber = 0;
int edges = 13;
// call DFS to mark the cycles
dfs_cycle(1, 0, color, mark, par);
// function to print the cycles
printCycles(edges, mark);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to print all the cycles
# in an undirected graph
N = 100000
# variables to be used
# in both functions
graph = [[] for i in range(N)]
cycles = [[] for i in range(N)]
# Function to mark the vertex with
# different colors for different cycles
def dfs_cycle(u, p, color: list,
mark: list, par: list):
global cyclenumber
# already (completely) visited vertex.
if color[u] == 2:
return
# seen vertex, but was not
# completely visited -> cycle detected.
# backtrack based on parents to
# find the complete cycle.
if color[u] == 1:
cyclenumber += 1
cur = p
mark[cur] = cyclenumber
# backtrack the vertex which are
# in the current cycle thats found
while cur != u:
cur = par[cur]
mark[cur] = cyclenumber
return
par[u] = p
# partially visited.
color[u] = 1
# simple dfs on graph
for v in graph[u]:
# if it has not been visited previously
if v == par[u]:
continue
dfs_cycle(v, u, color, mark, par)
# completely visited.
color[u] = 2
# add the edges to the graph
def addEdge(u, v):
graph[u].append(v)
graph[v].append(u)
# Function to print the cycles
def printCycles(edges, mark: list):
# push the edges that into the
# cycle adjacency list
for i in range(1, edges + 1):
if mark[i] != 0:
cycles[mark[i]].append(i)
# print all the vertex with same cycle
for i in range(1, cyclenumber + 1):
# Print the i-th cycle
print("Cycle Number %d:" % i, end = " ")
for x in cycles[i]:
print(x, end = " ")
print()
# Driver Code
if __name__ == "__main__":
# add edges
addEdge(1, 2)
addEdge(2, 3)
addEdge(3, 4)
addEdge(4, 6)
addEdge(4, 7)
addEdge(5, 6)
addEdge(3, 5)
addEdge(7, 8)
addEdge(6, 10)
addEdge(5, 9)
addEdge(10, 11)
addEdge(11, 12)
addEdge(11, 13)
addEdge(12, 13)
# arrays required to color the
# graph, store the parent of node
color = [0] * N
par = [0] * N
# mark with unique numbers
mark = [0] * N
# store the numbers of cycle
cyclenumber = 0
edges = 13
# call DFS to mark the cycles
dfs_cycle(1, 0, color, mark, par)
# function to print the cycles
printCycles(edges, mark)
# This code is contributed by
# sanjeev2552
C#
// C# program to print all
// the cycles in an undirected
// graph
using System;
using System.Collections.Generic;
class GFG{
static readonly int N = 100000;
// variables to be used
// in both functions
static List<int>[] graph =
new List<int>[N];
static List<int>[] cycles =
new List<int>[N];
static int cyclenumber;
// Function to mark the vertex with
// different colors for different cycles
static void dfs_cycle(int u, int p,
int[] color,
int[] mark,
int[] par)
{
// already (completely)
// visited vertex.
if (color[u] == 2)
{
return;
}
// seen vertex, but was not
// completely visited -> cycle
// detected. backtrack based on
// parents to find the complete
// cycle.
if (color[u] == 1)
{
cyclenumber++;
int cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which
// are in the current cycle
// thats found
while (cur != u)
{
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
foreach (int v in graph[u])
{
// if it has not been
// visited previously
if (v == par[u])
{
continue;
}
dfs_cycle(v, u, color,
mark, par);
}
// completely visited.
color[u] = 2;
}
// add the edges to the
// graph
static void addEdge(int u,
int v)
{
graph[u].Add(v);
graph[v].Add(u);
}
// Function to print the cycles
static void printCycles(int edges,
int []mark)
{
// push the edges that into the
// cycle adjacency list
for (int i = 1; i <= edges; i++)
{
if (mark[i] != 0)
cycles[mark[i]].Add(i);
}
// print all the vertex with
// same cycle
for (int i = 1;
i <= cyclenumber; i++)
{
// Print the i-th cycle
Console.Write("Cycle Number " + i + ":");
foreach (int x in cycles[i])
Console.Write(" " + x);
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
for (int i = 0; i < N; i++)
{
graph[i] = new List<int>();
cycles[i] = new List<int>();
}
// add edges
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 4);
addEdge(4, 6);
addEdge(4, 7);
addEdge(5, 6);
addEdge(3, 5);
addEdge(7, 8);
addEdge(6, 10);
addEdge(5, 9);
addEdge(10, 11);
addEdge(11, 12);
addEdge(11, 13);
addEdge(12, 13);
// arrays required to color
// the graph, store the parent
// of node
int[] color = new int[N];
int[] par = new int[N];
// mark with unique numbers
int[] mark = new int[N];
// store the numbers of cycle
cyclenumber = 0;
int edges = 13;
// call DFS to mark
// the cycles
dfs_cycle(1, 0, color,
mark, par);
// function to print the cycles
printCycles(edges, mark);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to print all
// the cycles in an undirected
// graph
var N = 100000;
// variables to be used
// in both functions
var graph = Array.from(Array(N), ()=>Array());
var cycles = Array.from(Array(N), ()=>Array());
var cyclenumber = 0;
// Function to mark the vertex with
// different colors for different cycles
function dfs_cycle(u, p, color, mark, par)
{
// already (completely)
// visited vertex.
if (color[u] == 2)
{
return;
}
// seen vertex, but was not
// completely visited -> cycle
// detected. backtrack based on
// parents to find the complete
// cycle.
if (color[u] == 1)
{
cyclenumber++;
var cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which
// are in the current cycle
// thats found
while (cur != u)
{
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
for(var v of graph[u])
{
// if it has not been
// visited previously
if (v == par[u])
{
continue;
}
dfs_cycle(v, u, color,
mark, par);
}
// completely visited.
color[u] = 2;
}
// add the edges to the
// graph
function addEdge(u, v)
{
graph[u].push(v);
graph[v].push(u);
}
// Function to print the cycles
function printCycles(edges, mark)
{
// push the edges that into the
// cycle adjacency list
for (var i = 1; i <= edges; i++)
{
if (mark[i] != 0)
cycles[mark[i]].push(i);
}
// print all the vertex with
// same cycle
for (var i = 1;
i <= cyclenumber; i++)
{
// Print the i-th cycle
document.write("Cycle Number " + i + ":");
for(var x of cycles[i])
document.write(" " + x);
document.write("<br>");
}
}
// Driver Code
// add edges
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 4);
addEdge(4, 6);
addEdge(4, 7);
addEdge(5, 6);
addEdge(3, 5);
addEdge(7, 8);
addEdge(6, 10);
addEdge(5, 9);
addEdge(10, 11);
addEdge(11, 12);
addEdge(11, 13);
addEdge(12, 13);
// arrays required to color
// the graph, store the parent
// of node
var color = Array(N).fill(0);
var par = Array(N).fill(0);
// mark with unique numbers
var mark = Array(N).fill(0);
// store the numbers of cycle
cyclenumber = 0;
var edges = 13;
// call DFS to mark
// the cycles
dfs_cycle(1, 0, color,
mark, par);
// function to print the cycles
printCycles(edges, mark);
</script>
Producción:
Cycle Number 1: 3 4 5 6 Cycle Number 2: 11 12 13
Complejidad temporal: O(N + M), donde N es el número de vértices y M es el número de aristas.
Espacio Auxiliar: O(N + M)