1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Trace of Graph as Adjacency Matrix Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
4.1.
What is the basic difference between a directed and undirected graph?
4.2.
How do you count edges on an undirected graph?
4.3.
Can an undirected graph have cycles?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

# Count the Number of Triangles in an Undirected Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

Counting the number of triangles in an undirected graph is a tricky question. It seems easy when we read it. But finding the proper logic and implementing it is hard to crack.

This article will discuss the solution to the problem of counting the number of triangles in an undirected graph. We will use a trace of the graph as adjacency and bitset and adjacency list approach to finding the problem's solution.

Now letâ€™s see the problem statement of this approach.

### Problem Statement

Given an Undirected simple graph, We need to find how many triangles it can have.

### Sample Examples

Example 1:

Input:

Output:

Explanation: The above example has four triangles. They are (0,2,4), (0,1,3), (1,2,3), (0,2,4).

Example 2:

Input:

Output:

Explanation: The above example has six triangles. They are (0,1,3), (1,2,3), (0,2,4), (0,1,2) (0,3,4), (2,3,4).

## Trace of Graph as Adjacency Matrix Approach

We will use a trace of the graph as an adjacency matrix. This will help us find the solution to the problem, count the number of triangles in an undirected graph. The trace of a matrix A is the sum of the elements on the main diagonal. The sum of a matrix's eigenvalues also equals the matrix's trace.

Letâ€™s see the algorithm of this approach.

### Algorithm

1. Let A be the adjacency matrix that represents the graph.
2. If we calculate A3. The number of triangles in the undirected graph equals to  trace(A3) / 6.
3. Here trace(A) is the sum of the elements on the main diagonal of the matrix A.
4. And the trace of a graph is represented as adjacency matrix A[G][G] is,
5. We will use the following formula to find the trace of matrices:

trace(A[G][G]) = A[0][0] + A[1][1] + .... + A[G-1][G-1]

Number of triangles = trace(A3) / 6

You can also read Detect cycle in an undirected graph here.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define G 4

//----------------Utility function for matrix multiplication----------------//
void multiplymatrices(int A[][G], int B[][G], int C[][G])
{
for (int i = 0; i < G; i++)
{
for (int j = 0; j < G; j++)
{
C[i][j] = 0;
for (int k = 0; k < G; k++)
C[i][j] += A[i][k]*B[k][j];
}
}
}

//----------------Utility function to calculate trace of a matrix----------------//
int Trace(int graph[][G])
{
int traceofmatrix = 0;
for (int i = 0; i < G; i++)
traceofmatrix += graph[i][i];
return traceofmatrix;
}

//----------------Utility function for calculating the number of triangles----------------//
int numoftriangle(int graph[][G])
{
// To Store graph 2

// To Store graph 3

for (int i = 0; i < G; ++i)
for (int j = 0; j < G; ++j)

// after this multiplication adj3 is

return traceofmatrix / 6;
}

//---------------------------Main Function---------------------------//
int main()
{
FAST;
int graph[G][G] = {{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0}
};

printf("Total number of Triangle in Graph : %d\n",
numoftriangle(graph));
return 0;
}``````

Output:

#### Time Complexity

The time complexity of the above-used approach is O(V3). As here most time-consuming part is the multiplication of the matrix, which contains three nested for loops.

#### Space Complexity

The time complexity of the above-used approach is O(V2). It is because we are storing a matrix of size V*V.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Bitset and Adjacency list Approach

In the bitset and adjacency list approach. We will use the bitwise operation & (and) on the adjacency list of i and j. And then, we count the number of ones.

### Algorithm

1. For each node in the graph. We will compute the corresponding adjacency list as a bitmask.
2. If two nodes, i & j, are adjacent. We will calculate the number of nodes adjacent to i & j. And then, we add it to the answer.
3. In the end, we will divide the answer by 6 to avoid duplicates.

### Implementation in C++

``````#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<string>
#include<bitset>
#include<algorithm>
#include<cstring>

using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define G 4

int main()
{
FAST;
int graph[][G] = {{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0}};

// We will create an adjacency list of the graph
// Here, set the bits at positions [i][j] & [j][i] to 1
for (int i = 0; i < G;i++)
for (int j = 0; j < G;j++)
if(graph[i][j])

int value = 0;

for (int i = 0; i < G;i++)
for (int j = 0; j < G;j++)

// when i & j are adjacent
// then compute the number of nodes which are adjacent to i & j
if(Bitset_Adjacency_List[i][j] == 1 && i != j)
{
}

// we will now divide the answer value by 6. It will help us to avoid duplicates
value /= 6;

cout << "The number of the Triangles in the Graph is: " << value;
}``````

Output:

#### Time Complexity

The time complexity of the above-used approach is O(V3). As here most time-consuming part is the multiplication of the matrix, which contains three nested for loops.

#### Space Complexity

The time complexity of the above-used approach is O(V2). It is because we are storing a matrix of size V*V.

Check out this problem - Check If A String Is Palindrome

### What is the basic difference between a directed and undirected graph?

The edges in a directed graph have a specific direction (one-directional). But edges in an undirected graph are bidirectional.

### How do you count edges on an undirected graph?

The number of edges in a simple undirected graph is n(n-1)/2. It is the maximum number of edges in a simple undirected graph. It is not the number of edges for every such graph.

### Can an undirected graph have cycles?

An undirected graph is acyclic (i.e., a forest) if a DFS yields no back edges. Since back edges are those edges ( u, v ) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges mean there are only tree edges, so there is no cycle.

## Conclusion

This article briefly discussed the problem of counting the number of triangles in an undirected graph.

We hope that this blog has helped you enhance your knowledge about the problem of counting the number of triangles in an undirected graph and if you would like to learn more, check out our articles Minimize the number of weakly connected nodesCount BST subtrees that lie in a given rangeConvert BST to the Greatest Sum TreeReplace each node in a binary tree with a sum of its in order predecessor and successor, and Print Nodes between two given Level Numbers of a Binary Tree

You can also refer to our guided path on the basics of java and many more on our Website.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series. You can also participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy learning!

Live masterclass