Number of Triangles in a Directed and Undirected Graph
Problem Statement
Given a graph (directed or undirected), count the total number of triangles. A triangle is a set of three vertices where each pair is connected by an edge.
Example (Undirected):
- Input:
V = 4, edges = [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)] - Output:
4triangles
Example (Directed):
- Input:
V = 4, edges = [(0,1),(1,2),(2,0),(0,3),(3,1)] - Output:
1triangle (0→1→2→0)
Noob-Friendly Explanation
Imagine three friends who all know each other. That's a triangle! In a group of people, a triangle is any trio where everyone is friends with everyone else.
For an undirected graph, we check all sets of three people. If all three edges exist, that's a triangle. For directed graphs, we look for directed cycles of length 3.
Approach 1: Brute Force (Check All Triples)
Intuition
Check every possible combination of three vertices. If all three edges between them exist, it's a triangle.
Algorithm
- For each triple (i, j, k) where i < j < k:
- Check if edges (i,j), (j,k), and (i,k) all exist.
- If yes, count it as a triangle.
For directed graphs, check all ordered triples (i, j, k) for directed edges i→j, j→k, k→i.
public class TrianglesBrute {
// For undirected graph
public static int countTrianglesUndirected(int V, int[][] adj) {
int count = 0;
for (int i = 0; i < V; i++) {
for (int j = i + 1; j < V; j++) {
for (int k = j + 1; k < V; k++) {
if (adj[i][j] == 1 && adj[j][k] == 1 && adj[i][k] == 1) {
count++;
}
}
}
}
return count;
}
// For directed graph
public static int countTrianglesDirected(int V, int[][] adj) {
int count = 0;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (i == j) continue;
for (int k = 0; k < V; k++) {
if (k == i || k == j) continue;
if (adj[i][j] == 1 && adj[j][k] == 1 && adj[k][i] == 1) {
count++;
}
}
}
}
// Each triangle is counted 3 times (3 starting vertices)
return count / 3;
}
public static void main(String[] args) {
// Undirected graph
int V = 4;
int[][] adj = {
{0,1,1,1},
{1,0,1,1},
{1,1,0,1},
{1,1,1,0}
};
System.out.println("Undirected triangles: " + countTrianglesUndirected(V, adj));
// Directed graph
int[][] adjDir = {
{0,1,0,1},
{0,0,1,0},
{1,0,0,0},
{0,1,0,0}
};
System.out.println("Directed triangles: " + countTrianglesDirected(V, adjDir));
}
}Complexity Analysis
- Time Complexity: O(V³) - checking all triples of vertices
- Space Complexity: O(V²) - for the adjacency matrix
Approach 2: Optimal (Matrix Multiplication / Trace Method)
Intuition
Using the adjacency matrix A, the number of triangles can be computed using the trace of A³ (A cubed). The entry A³[i][i] counts the number of closed walks of length 3 starting and ending at vertex i. The total number of triangles is trace(A³)/6 for undirected graphs (each triangle is counted 6 times: 3 starting vertices × 2 directions) and trace(A³)/3 for directed graphs.
Algorithm
- Compute A² = A × A (matrix multiplication).
- Compute A³ = A² × A.
- Sum the diagonal elements of A³.
- Divide by 6 (undirected) or 3 (directed).
public class TrianglesOptimal {
public static int countTrianglesUndirected(int V, int[][] adj) {
// Compute A³
int[][] a2 = multiply(adj, adj, V);
int[][] a3 = multiply(a2, adj, V);
// Trace of A³
int trace = 0;
for (int i = 0; i < V; i++) {
trace += a3[i][i];
}
return trace / 6; // each triangle counted 6 times
}
public static int countTrianglesDirected(int V, int[][] adj) {
int[][] a2 = multiply(adj, adj, V);
int[][] a3 = multiply(a2, adj, V);
int trace = 0;
for (int i = 0; i < V; i++) {
trace += a3[i][i];
}
return trace / 3; // each triangle counted 3 times
}
static int[][] multiply(int[][] A, int[][] B, int V) {
int[][] C = new int[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
for (int k = 0; k < V; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
public static void main(String[] args) {
// Undirected graph
int V = 4;
int[][] adj = {
{0,1,1,1},
{1,0,1,1},
{1,1,0,1},
{1,1,1,0}
};
System.out.println("Undirected triangles: " + countTrianglesUndirected(V, adj));
// Directed graph
int[][] adjDir = {
{0,1,0,1},
{0,0,1,0},
{1,0,0,0},
{0,1,0,0}
};
System.out.println("Directed triangles: " + countTrianglesDirected(V, adjDir));
}
}Complexity Analysis
- Time Complexity: O(V³) - two matrix multiplications, each O(V³)
- Space Complexity: O(V²) - for the matrices