Número de triángulos en gráficos dirigidos y no dirigidos

Dado un gráfico, cuente el número de triángulos en él. El grafo puede ser dirigido o no dirigido.

Ejemplo: 

Input: digraph[V][V] = { {0, 0, 1, 0},
                        {1, 0, 0, 1},
                        {0, 1, 0, 0},
                        {0, 0, 1, 0}
                      };
Output: 2
Give adjacency matrix represents following 
directed graph.

Hemos discutido un método basado en la traza del gráfico que funciona para gráficos no dirigidos. En esta publicación, se analiza un nuevo método que es más simple y funciona tanto para gráficos dirigidos como no dirigidos.
La idea es usar tres bucles anidados para considerar cada triplete (i, j, k) y verificar la condición anterior (hay un borde de i a j, j a k y k a i) 
Sin embargo, en un gráfico no dirigido , el El triplete (i, j, k) se puede permutar para dar seis combinaciones (consulte la publicación anterior para obtener más detalles). Por lo tanto, dividimos el conteo total por 6 para obtener el número real de triángulos. 
En caso de grafo dirigido, el número de permutaciones sería 3 (a medida que el orden de los Nodes se vuelva relevante). Por lo tanto, en este caso, el número total de triángulos se obtendrá dividiendo el recuento total por 3. Por ejemplo, considere el gráfico dirigido que se muestra a continuación. 

A continuación se muestra la implementación. 

// C++ program to count triangles
// in a graph. The program is for
// adjacency matrix representation
// of the graph.
#include<bits/stdc++.h>
 
// Number of vertices in the graph
#define V 4
 
using namespace std;
 
// function to calculate the
// number of triangles in a
// simple directed/undirected
// graph. isDirected is true if
// the graph is directed, its
// false otherwise
int countTriangle(int graph[V][V],
                  bool isDirected)
{
    // Initialize result
    int count_Triangle = 0;
 
    // Consider every possible
    // triplet of edges in graph
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            for (int k = 0; k < V; k++)
            {
               // Check the triplet if
               // it satisfies the condition
               if (graph[i][j] && graph[j][k]
                               && graph[k][i])
                  count_Triangle++;
             }
        }
    }
 
    // If graph is directed ,
    // division is done by 3,
    // else division by 6 is done
    isDirected? count_Triangle /= 3 :
                count_Triangle /= 6;
 
    return count_Triangle;
}
 
//driver function to check the program
int main()
{
    // Create adjacency matrix
    // of an undirected graph
    int graph[][V] = { {0, 1, 1, 0},
                       {1, 0, 1, 1},
                       {1, 1, 0, 1},
                       {0, 1, 1, 0}
                     };
 
    // Create adjacency matrix
    // of a directed graph
    int digraph[][V] = { {0, 0, 1, 0},
                        {1, 0, 0, 1},
                        {0, 1, 0, 0},
                        {0, 0, 1, 0}
                       };
 
    cout << "The Number of triangles in undirected graph : "
         << countTriangle(graph, false);
    cout << "\n\nThe Number of triangles in directed graph : "
         << countTriangle(digraph, true);
 
    return 0;
}

// Java program to count triangles
// in a graph.  The program is
// for adjacency matrix
// representation of the graph.
import java.io.*;
 
class GFG {
 
    // Number of vertices in the graph
    int V = 4;
 
    // function to calculate the number
    // of triangles in a simple
    // directed/undirected graph. isDirected
    // is true if the graph is directed,
    // its false otherwise.
    int countTriangle(int graph[][],
                      boolean isDirected)
   {
       // Initialize result
       int count_Triangle = 0;
 
       // Consider every possible
       // triplet of edges in graph
       for (int i = 0; i < V; i++)
       {
           for (int j = 0; j < V; j++)
           {
               for (int k=0; k<V; k++)
               {
                  // Check the triplet if it
                  // satisfies the condition
                  if (graph[i][j] == 1 &&
                      graph[j][k] == 1 &&
                      graph[k][i] == 1)
                      count_Triangle++;
               }
           }
       }
  
       // If graph is directed , division
       // is done by 3 else division
       // by 6 is done
       if(isDirected == true)
       {
           count_Triangle /= 3;
       }
       else
       {
           count_Triangle /= 6;
       }
       return count_Triangle;
   }
  
   // Driver code
    public static void main(String args[])
   {
        
       // Create adjacency matrix
       // of an undirected graph
       int graph[][] = {{0, 1, 1, 0},
                        {1, 0, 1, 1},
                        {1, 1, 0, 1},
                        {0, 1, 1, 0}
                       };
     
       // Create adjacency matrix
       // of a directed graph
       int digraph[][] = { {0, 0, 1, 0},
                           {1, 0, 0, 1},
                           {0, 1, 0, 0},
                           {0, 0, 1, 0}
                         };
       
      GFG obj = new GFG();
  
    System.out.println("The Number of triangles "+
                       "in undirected graph : " +
                        obj.countTriangle(graph, false));
 
    System.out.println("\n\nThe Number of triangles"+
                       " in directed graph : "+
                       obj.countTriangle(digraph, true));
 
   }
}
 
// This code is contributed by Anshika Goyal.

# Python program to count triangles
# in a graph.  The program is
# for adjacency matrix
# representation of the graph.
 
 
# function to calculate the number
# of triangles in a simple
# directed/undirected graph.
# isDirected is true if the graph
# is directed, its false otherwise
def countTriangle(g, isDirected):
    nodes = len(g)
    count_Triangle = 0
     
    # Consider every possible
    # triplet of edges in graph
    for i in range(nodes):
        for j in range(nodes):
            for k in range(nodes):
                 
                # check the triplet
                # if it satisfies the condition
                if(i != j and i != k
                   and j != k and
                   g[i][j] and g[j][k]
                   and g[k][i]):
                    count_Triangle += 1
     
    # If graph is directed , division is done by 3
    # else division by 6 is done
    if isDirected:
      return count_Triangle//3 
    else: return count_Triangle//6
 
 
# Create adjacency matrix of an undirected graph
graph = [[0, 1, 1, 0],
         [1, 0, 1, 1],
         [1, 1, 0, 1],
         [0, 1, 1, 0]]
# Create adjacency matrix of a directed graph
digraph = [[0, 0, 1, 0],
           [1, 0, 0, 1],
           [0, 1, 0, 0],
           [0, 0, 1, 0]]
 
print("The Number of triangles in undirected graph : %d" %
      countTriangle(graph, False))
 
print("The Number of triangles in directed graph : %d" %
      countTriangle(digraph, True))
 
# This code is contributed by Neelam Yadav

// C# program to count triangles in a graph.
// The program is for adjacency matrix
// representation of the graph.
using System;
 
class GFG {
 
    // Number of vertices in the graph
    const int V = 4;
 
    // function to calculate the
    // number of triangles in a
    // simple directed/undirected
    // graph. isDirected is true if
    // the graph is directed, its
    // false otherwise
    static int countTriangle(int[, ] graph, bool isDirected)
    {
        // Initialize result
        int count_Triangle = 0;
 
        // Consider every possible
        // triplet of edges in graph
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                for (int k = 0; k < V; k++)
                {
                    // check the triplet if
                    // it satisfies the condition
                    if (graph[i, j] != 0
                        && graph[j, k] != 0
                        && graph[k, i] != 0)
                        count_Triangle++;
                }
            }
        }
 
        // if graph is directed ,
        // division is done by 3,
        // else division by 6 is done
        if (isDirected != false)
            count_Triangle = count_Triangle / 3;
        else
            count_Triangle = count_Triangle / 6;
 
        return count_Triangle;
    }
 
    // Driver code
    static void Main()
    {
 
        // Create adjacency matrix
        // of an undirected graph
        int[, ] graph = new int[4, 4] { { 0, 1, 1, 0 },
                                        { 1, 0, 1, 1 },
                                        { 1, 1, 0, 1 },
                                        { 0, 1, 1, 0 } };
 
        // Create adjacency matrix
        // of a directed graph
        int[, ] digraph = new int[4, 4] { { 0, 0, 1, 0 },
                                          { 1, 0, 0, 1 },
                                          { 0, 1, 0, 0 },
                                          { 0, 0, 1, 0 } };
 
        Console.Write("The Number of triangles"
                      + " in undirected graph : "
                      + countTriangle(graph, false));
 
        Console.Write("\n\nThe Number of "
                      + "triangles in directed graph : "
                      + countTriangle(digraph, true));
    }
}
 
// This code is contributed by anuj_67

<?php
// PHP program to count triangles
// in a graph. The program is for
// adjacency matrix representation
// of the graph.
 
// Number of vertices in the graph
$V = 4;
 
// function to calculate the
// number of triangles in a
// simple directed/undirected
// graph. isDirected is true if
// the graph is directed, its
// false otherwise
function countTriangle($graph,
                       $isDirected)
{
    global $V;
     
    // Initialize result
    $count_Triangle = 0;
 
    // Consider every possible
    // triplet of edges in graph
    for($i = 0; $i < $V; $i++)
    {
        for($j = 0; $j < $V; $j++)
        {
            for($k = 0; $k < $V; $k++)
            {
                 
                // check the triplet if
                // it satisfies the condition
                if ($graph[$i][$j] and $graph[$j][$k]
                                   and $graph[$k][$i])
                    $count_Triangle++;
            }
        }
    }
 
    // if graph is directed ,
    // division is done by 3,
    // else division by 6 is done
    $isDirected? $count_Triangle /= 3 :
                 $count_Triangle /= 6;
 
    return $count_Triangle;
}
 
    // Driver Code
    // Create adjacency matrix
    // of an undirected graph
    $graph = array(array(0, 1, 1, 0),
                   array(1, 0, 1, 1),
                   array(1, 1, 0, 1),
                   array(0, 1, 1, 0));
 
    // Create adjacency matrix
    // of a directed graph
    $digraph = array(array(0, 0, 1, 0),
                     array(1, 0, 0, 1),
                     array(0, 1, 0, 0),
                     array(0, 0, 1, 0));
         
    echo "The Number of triangles in undirected graph : "
                        , countTriangle($graph, false);
    echo "\nThe Number of triangles in directed graph : "
                        , countTriangle($digraph, true);
                         
// This code is contributed by anuj_67
?>

<script>
 
// Javascript program to count triangles
// in a graph. The program is for
// adjacency matrix representation
// of the graph.
 
// Number of vertices in the graph
let V = 4;
 
// Function to calculate the
// number of triangles in a
// simple directed/undirected
// graph. isDirected is true if
// the graph is directed, its
// false otherwise
function countTriangle(graph, isDirected)
{
     
    // Initialize result
    let count_Triangle = 0;
 
    // Consider every possible
    // triplet of edges in graph
    for(let i = 0; i < V; i++)
    {
        for(let j = 0; j < V; j++)
        {
            for(let k = 0; k < V; k++)
            {
                // Check the triplet if
                // it satisfies the condition
                if (graph[i][j] && graph[j][k] &&
                    graph[k][i])
                    count_Triangle++;
             }
        }
    }
 
    // If graph is directed ,
    // division is done by 3,
    // else division by 6 is done
    isDirected ? count_Triangle /= 3 :
                 count_Triangle /= 6;
 
    return count_Triangle;
}
 
// Driver code
 
// Create adjacency matrix
// of an undirected graph
let graph = [ [ 0, 1, 1, 0 ],
              [ 1, 0, 1, 1 ],
              [ 1, 1, 0, 1 ],
              [ 0, 1, 1, 0 ] ];
 
// Create adjacency matrix
// of a directed graph
let digraph = [ [ 0, 0, 1, 0 ],
                [ 1, 0, 0, 1 ],
                [ 0, 1, 0, 0 ],
                [ 0, 0, 1, 0 ] ];
 
document.write("The Number of triangles " +
               "in undirected graph : " +
               countTriangle(graph, false) +
               "</br></br>");
document.write("The Number of triangles " +
               "in directed graph : " +
               countTriangle(digraph, true));
                
// This code is contributed by divyesh072019
 
</script>

The Number of triangles in undirected graph : 2

The Number of triangles in directed graph : 2

Comparación de este enfoque con el enfoque anterior : 
Ventajas: 

• No es necesario calcular Trace.
• No se requiere la multiplicación de arrays.
• No se requieren arrays auxiliares, por lo tanto, optimizadas en el espacio.
• Funciona para grafos dirigidos.

Desventajas: 

• La complejidad del tiempo es O(n ³ ) y no se puede reducir más.

Este artículo es una contribución de Ashutosh Kumar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.