Número de componentes de un solo ciclo en un gráfico no dirigido

Posted on by Rudeus Greyrat

Dado un conjunto de vértices ‘n’ y aristas ‘m’ de un gráfico simple no dirigido (sin aristas paralelas y sin bucle), encuentre el número de componentes de un solo ciclo presentes en el gráfico. Un componente cíclico único es un gráfico de n Nodes que contiene un solo ciclo a través de todos los Nodes del componente.
Ejemplo: 
 

Let us consider the following graph with 15 vertices.

Input: V = 15, E = 14
       1 10  // edge 1
       1 5   // edge 2
       5 10  // edge 3
       2 9   // ..
       9 15  // ..
       2 15  // ..
       2 12  // ..
       12 15 // ..
       13 8  // ..
       6 14  // ..
       14 3  // ..
       3 7   // ..
       7 11  // edge 13
       11 6  // edge 14
Output :2
In the above-mentioned example, the two 
single-cyclic-components are composed of 
vertices (1, 10, 5) and (6, 11, 7, 3, 14) 
respectively.

Ahora podemos ver fácilmente que un componente de un solo ciclo es un componente conectado donde cada vértice tiene el grado de dos. 
Por lo tanto, para resolver este problema, primero identificamos todos los componentes conectados del gráfico desconectado. Para esto, utilizamos el algoritmo de búsqueda primero en profundidad. Para que el algoritmo DFS funcione, se requiere mantener una array ‘encontrada’ para llevar un registro de todos los vértices que ha descubierto la función recursiva DFS. Una vez que se descubren todos los elementos de un componente conectado en particular (como los vértices (9, 2, 15, 12) forman un componente gráfico conectado), verificamos si todos los vértices del componente tienen el grado igual a dos. En caso afirmativo, aumentamos la variable de contador ‘recuento’, que denota el número de componentes de un solo ciclo que se encuentran en el gráfico dado. Para mantener una cuenta del componente con el que estamos tratando actualmente, también podemos usar una array de vectores ‘curr_graph’.
 

C++

// CPP program to find single cycle components
// in a graph.
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100000;
 
// degree of all the vertices
int degree[N];
 
// to keep track of all the vertices covered
// till now
bool found[N];
 
// all the vertices in a particular
// connected component of the graph
vector<int> curr_graph;
 
// adjacency list
vector<int> adj_list[N];
 
// depth-first traversal to identify all the
// nodes in a particular connected graph
// component
void DFS(int v)
{
    found[v] = true;
    curr_graph.push_back(v);
    for (int it : adj_list[v])
        if (!found[it])
            DFS(it);
}
 
// function to add an edge in the graph
void addEdge(vector<int> adj_list[N], int src,
             int dest)
{
    // for index decrement both src and dest.
    src--, dest--;
    adj_list[src].push_back(dest);
    adj_list[dest].push_back(src);
    degree[src]++;
    degree[dest]++;
}
 
int countSingleCycles(int n, int m)
{
    // count of cycle graph components
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (!found[i]) {
            curr_graph.clear();
            DFS(i);
 
            // traversing the nodes of the
            // current graph component
            int flag = 1;
            for (int v : curr_graph) {
                if (degree[v] == 2)
                    continue;
                else {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                count++;
            }
        }
    }
    return(count);
}
 
int main()
{
    // n->number of vertices
    // m->number of edges
    int n = 15, m = 14;
    addEdge(adj_list, 1, 10);
    addEdge(adj_list, 1, 5);
    addEdge(adj_list, 5, 10);
    addEdge(adj_list, 2, 9);
    addEdge(adj_list, 9, 15);
    addEdge(adj_list, 2, 15);
    addEdge(adj_list, 2, 12);
    addEdge(adj_list, 12, 15);
    addEdge(adj_list, 13, 8);
    addEdge(adj_list, 6, 14);
    addEdge(adj_list, 14, 3);
    addEdge(adj_list, 3, 7);
    addEdge(adj_list, 7, 11);
    addEdge(adj_list, 11, 6);
 
    cout << countSingleCycles(n, m);
 
    return 0;
}

Java

// Java program to find single cycle components
// in a graph.
import java.util.*;
 
class GFG
{
 
static int N = 100000;
 
// degree of all the vertices
static int degree[] = new int[N];
 
// to keep track of all the vertices covered
// till now
static boolean found[] = new boolean[N];
 
// all the vertices in a particular
// connected component of the graph
static Vector<Integer> curr_graph = new Vector<Integer>();
 
// adjacency list
static Vector<Vector<Integer>> adj_list = new Vector<Vector<Integer>>();
 
// depth-first traversal to identify all the
// nodes in a particular connected graph
// component
static void DFS(int v)
{
    found[v] = true;
    curr_graph.add(v);
    for (int it = 0 ;it < adj_list.get(v).size(); it++)
        if (!found[adj_list.get(v).get(it)])
            DFS(adj_list.get(v).get(it));
}
 
// function to add an edge in the graph
static void addEdge( int src,int dest)
{
    // for index decrement both src and dest.
    src--; dest--;
    adj_list.get(src).add(dest);
    adj_list.get(dest).add(src);
    degree[src]++;
    degree[dest]++;
}
 
static int countSingleCycles(int n, int m)
{
    // count of cycle graph components
    int count = 0;
    for (int i = 0; i < n; ++i)
    {
 
        if (!found[i])
        {
            curr_graph.clear();
             
            DFS(i);
 
            // traversing the nodes of the
            // current graph component
            int flag = 1;
            for (int v = 0 ; v < curr_graph.size(); v++)
            {
                if (degree[curr_graph.get(v)] == 2)
                    continue;
                else
                {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
            {
                count++;
            }
        }
    }
    return(count);
}
 
// Driver code
public static void main(String args[])
{
     
    for(int i = 0; i < N + 1; i++)
    adj_list.add(new Vector<Integer>());
     
    // n->number of vertices
    // m->number of edges
    int n = 15, m = 14;
    addEdge( 1, 10);
    addEdge( 1, 5);
    addEdge( 5, 10);
    addEdge( 2, 9);
    addEdge( 9, 15);
    addEdge( 2, 15);
    addEdge( 2, 12);
    addEdge( 12, 15);
    addEdge( 13, 8);
    addEdge( 6, 14);
    addEdge( 14, 3);
    addEdge( 3, 7);
    addEdge( 7, 11);
    addEdge( 11, 6);
     
 
    System.out.println(countSingleCycles(n, m));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to find single
# cycle components in a graph.
N = 100000
 
# degree of all the vertices
degree = [0] * N
 
# to keep track of all the
# vertices covered till now
found = [None] * N
 
# All the vertices in a particular
# connected component of the graph
curr_graph = []
 
# adjacency list
adj_list = [[] for i in range(N)]
 
# depth-first traversal to identify
# all the nodes in a particular
# connected graph component
def DFS(v):
 
    found[v] = True
    curr_graph.append(v)
     
    for it in adj_list[v]:
        if not found[it]:
            DFS(it)
 
# function to add an edge in the graph
def addEdge(adj_list, src, dest):
 
    # for index decrement both src and dest.
    src, dest = src - 1, dest - 1
    adj_list[src].append(dest)
    adj_list[dest].append(src)
    degree[src] += 1
    degree[dest] += 1
 
def countSingleCycles(n, m):
 
    # count of cycle graph components
    count = 0
    for i in range(0, n):
        if not found[i]:
            curr_graph.clear()
            DFS(i)
 
            # traversing the nodes of the
            # current graph component
            flag = 1
            for v in curr_graph:
                if degree[v] == 2:
                    continue
                else:
                    flag = 0
                    break
                 
            if flag == 1:
                count += 1
     
    return count
 
# Driver Code
if __name__ == "__main__":
 
    # n->number of vertices
    # m->number of edges
    n, m = 15, 14
    addEdge(adj_list, 1, 10)
    addEdge(adj_list, 1, 5)
    addEdge(adj_list, 5, 10)
    addEdge(adj_list, 2, 9)
    addEdge(adj_list, 9, 15)
    addEdge(adj_list, 2, 15)
    addEdge(adj_list, 2, 12)
    addEdge(adj_list, 12, 15)
    addEdge(adj_list, 13, 8)
    addEdge(adj_list, 6, 14)
    addEdge(adj_list, 14, 3)
    addEdge(adj_list, 3, 7)
    addEdge(adj_list, 7, 11)
    addEdge(adj_list, 11, 6)
 
    print(countSingleCycles(n, m))
 
# This code is contributed by Rituraj Jain

C#

// C# program to find single cycle components
// in a graph.
using System;
using System.Collections.Generic;
     
class GFG
{
static int N = 100000;
 
// degree of all the vertices
static int []degree = new int[N];
 
// to keep track of all the vertices covered
// till now
static bool []found = new bool[N];
 
// all the vertices in a particular
// connected component of the graph
static List<int> curr_graph = new List<int>();
 
// adjacency list
static List<List<int>> adj_list = new List<List<int>>();
 
// depth-first traversal to identify all the
// nodes in a particular connected graph
// component
static void DFS(int v)
{
    found[v] = true;
    curr_graph.Add(v);
    for (int it = 0; it < adj_list[v].Count; it++)
        if (!found[adj_list[v][it]])
            DFS(adj_list[v][it]);
}
 
// function to add an edge in the graph
static void addEdge(int src,int dest)
{
    // for index decrement both src and dest.
    src--; dest--;
    adj_list[src].Add(dest);
    adj_list[dest].Add(src);
    degree[src]++;
    degree[dest]++;
}
 
static int countSingleCycles(int n, int m)
{
    // count of cycle graph components
    int count = 0;
    for (int i = 0; i < n; ++i)
    {
        if (!found[i])
        {
            curr_graph.Clear();
             
            DFS(i);
 
            // traversing the nodes of the
            // current graph component
            int flag = 1;
            for (int v = 0 ; v < curr_graph.Count; v++)
            {
                if (degree[curr_graph[v]] == 2)
                    continue;
                else
                {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
            {
                count++;
            }
        }
    }
    return(count);
}
 
// Driver code
public static void Main(String []args)
{
    for(int i = 0; i < N + 1; i++)
    adj_list.Add(new List<int>());
     
    // n->number of vertices
    // m->number of edges
    int n = 15, m = 14;
    addEdge(1, 10);
    addEdge(1, 5);
    addEdge(5, 10);
    addEdge(2, 9);
    addEdge(9, 15);
    addEdge(2, 15);
    addEdge(2, 12);
    addEdge(12, 15);
    addEdge(13, 8);
    addEdge(6, 14);
    addEdge(14, 3);
    addEdge(3, 7);
    addEdge(7, 11);
    addEdge(11, 6);
     
    Console.WriteLine(countSingleCycles(n, m));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript program to find single cycle components
// in a graph.
 
let N = 100000;
 
// degree of all the vertices
let degree=new Array(N);
for(let i=0;i<N;i++)
    degree[i]=0;
// to keep track of all the vertices covered
// till now
let found=new Array(N);
for(let i=0;i<N;i++)
    found[i]=0;
 
// all the vertices in a particular
// connected component of the graph
let curr_graph = [];
 
// adjacency list
let adj_list = [];
 
// depth-first traversal to identify all the
// nodes in a particular connected graph
// component
function DFS(v)
{
    found[v] = true;
    curr_graph.push(v);
    for (let it = 0 ;it < adj_list[v].length; it++)
        if (!found[adj_list[v][it]])
            DFS(adj_list[v][it]);
}
 
// function to add an edge in the graph
function addEdge(src,dest)
{
    // for index decrement both src and dest.
    src--; dest--;
    adj_list[src].push(dest);
    adj_list[dest].push(src);
    degree[src]++;
    degree[dest]++;
}
 
function countSingleCycles(n,m)
{
    // count of cycle graph components
    let count = 0;
    for (let i = 0; i < n; ++i)
    {
   
        if (!found[i])
        {
            curr_graph=[];
               
            DFS(i);
   
            // traversing the nodes of the
            // current graph component
            let flag = 1;
            for (let v = 0 ; v < curr_graph.length; v++)
            {
                if (degree[curr_graph[v]] == 2)
                    continue;
                else
                {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
            {
                count++;
            }
        }
    }
    return(count);
}
 
// Driver code
for(let i = 0; i < N + 1; i++)
    adj_list.push([]);
 
// n->number of vertices
// m->number of edges
let n = 15, m = 14;
addEdge( 1, 10);
addEdge( 1, 5);
addEdge( 5, 10);
addEdge( 2, 9);
addEdge( 9, 15);
addEdge( 2, 15);
addEdge( 2, 12);
addEdge( 12, 15);
addEdge( 13, 8);
addEdge( 6, 14);
addEdge( 14, 3);
addEdge( 3, 7);
addEdge( 7, 11);
addEdge( 11, 6);
 
 
document.write(countSingleCycles(n, m));
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

2

 

Por lo tanto, se encuentra el número total de componentes del gráfico de ciclo.
 

Publicación traducida automáticamente

Artículo escrito por PiyushKumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *