Count triangles in a graph
Problem
Count the triangles (sets of three mutually connected vertices) in a graph given as an adjacency matrix. Note the directed and undirected counts differ in how duplicates are divided out.
Example 1
Input: undirected [[0,1,1,0], [1,0,1,1], [1,1,0,1], [0,1,1,0]] Output: 2
{0,1,2} and {1,2,3}.
Also asked as: Number of Triangles in a Directed and Undirected Graph
Test cases
Case 1
Input: [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]] Expected: 2
Case 2
Input: [[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]] Expected: 4
Case 3
Input: [[0,1,1],[1,0,1],[1,1,0]] Expected: 1
Case 4
Input: [[0,1],[1,0]] Expected: 0
View solutionHide solution1 approach
1. Trace of A³ / adjacency-matrix cubing
Time O(V³)Space O(V²)
The number of closed walks of length 3 is trace(A³). Divide by 6 for an undirected graph, by 3 for a directed one.
function countTriangles(A, directed = false) { const n = A.length; const mul = (X, Y) => { const Z = Array.from({ length: n }, () => new Array(n).fill(0)); for (let i = 0; i < n; i++) for (let k = 0; k < n; k++) if (X[i][k]) for (let j = 0; j < n; j++) Z[i][j] += X[i][k] * Y[k][j]; return Z; }; const A3 = mul(mul(A, A), A); let trace = 0; for (let i = 0; i < n; i++) trace += A3[i][i]; return trace / (directed ? 3 : 6);}