Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Bitset and Adjacency list Approach 
3.1.
Algorithm 
3.2.
Implementation in C++
3.2.1.
Time Complexity 
3.2.2.
Space Complexity 
4.
Frequently Asked Questions 
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.

Count the Number of Triangles in an Undirected Graph

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.

problem statement

Sample Examples 

Example 1:

Input:

input

Output:

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:

input

Output:

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
			int adj2[G][G];

		// To Store graph 3
			int adj3[G][G];

			for (int i = 0; i < G; ++i)
				for (int j = 0; j < G; ++j)
					adj2[i][j] = adj3[i][j] = 0;

		// adj2 is graph 2, now printMatrix(adj2);
			multiplymatrices(graph, graph, adj2);

		// after this multiplication adj3 is
			multiplymatrices(graph, adj2, adj3);

		int traceofmatrix = Trace(adj3);
		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:

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
		vector<bitset<G>> Bitset_Adjacency_List(G);
			for (int i = 0; i < G;i++)
				for (int j = 0; j < G;j++)
					if(graph[i][j])
					Bitset_Adjacency_List[i][j] = 1,
					Bitset_Adjacency_List[j][i] = 1;

			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)
			{
				bitset<G> Mask = Bitset_Adjacency_List[i] & Bitset_Adjacency_List[j];
				value += Mask.count();
			}

	// 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:

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

Frequently Asked Questions 

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!

Previous article
Construct Binary Palindrome by Repeated Appending and Trimming
Next article
Vertex Cover Problem
Live masterclass