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++
// 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
// 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.
Python3
# 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#
// 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
// 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
?>
Javascript
<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>
Producción
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 3 ) 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.
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