Number of Triangles in an Undirected Graph | A C ++ program for finding number of triangles in an Undirected Graph . The program is for adjacency matrix representation of the graph ; Number of vertices in the graph ; Utility function for matrix multiplication ; Utility function to calculate trace of a matrix ( sum ofdiagnonal elements ) ; Utility function for calculating number of triangles in graph ; To Store graph ^ 2 ; To Store graph ^ 3 ; Initialising aux matrices with 0 ; aux2 is graph ^ 2 now printMatrix ( aux2 ) ; ; after this multiplication aux3 is graph ^ 3 printMatrix ( aux3 ) ; ; driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define V  4 NEW_LINE void multiply ( int A [ ] [ V ] , int B [ ] [ V ] , int C [ ] [ V ] ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { C [ i ] [ j ] = 0 ; for ( int k = 0 ; k < V ; k ++ ) C [ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ] ; } } } int getTrace ( int graph [ ] [ V ] ) { int trace = 0 ; for ( int i = 0 ; i < V ; i ++ ) trace += graph [ i ] [ i ] ; return trace ; } int triangleInGraph ( int graph [ ] [ V ] ) { int aux2 [ V ] [ V ] ; int aux3 [ V ] [ V ] ; for ( int i = 0 ; i < V ; ++ i ) for ( int j = 0 ; j < V ; ++ j ) aux2 [ i ] [ j ] = aux3 [ i ] [ j ] = 0 ; multiply ( graph , graph , aux2 ) ; multiply ( graph , aux2 , aux3 ) ; int trace = getTrace ( aux3 ) ; return trace / 6 ; } int main ( ) { int graph [ V ] [ V ] = { { 0 , 1 , 1 , 0 } , { 1 , 0 , 1 , 1 } , { 1 , 1 , 0 , 1 } , { 0 , 1 , 1 , 0 } } ; printf ( " Total ▁ number ▁ of ▁ Triangle ▁ in ▁ Graph ▁ : ▁ % d STRNEWLINE " , triangleInGraph ( graph ) ) ; return 0 ; }