Number of Triangles in an Undirected Graph | GeeksForGeeks

This video is contributed by Pranav Nambiar.

[hussainrangwala]

You should also walk through how you got aux2 and aux3 and why does one need two matrices. I think that would be helpful

[sujoyseal]

See if you have a graph of n vertices, the maximal length of cycle can n. Also, for a cycle we need at least 3 vertices. So, run a loop from 3 to n inclusive. Inside this loop, find out A^i since you need to have a cycle length of i vertices. Now calculate [trace(A^i)]/(n*2) which is your final answer. Use strassesns algo to calculate A^i. Folks, we are using trace of the matrix since we are interested in cycles. A[i][i] gives you all distinct paths from i to i . Now, sum it over i=0 to i=n-1 which is trace. Now divide it by (2*n) if its undirected and divide by n if directed

[adityarana]

i couldn't understand the actual logic behind the code/

[Kaushikvel]

Awesome. It was a very good explanation

[jacobotapia]

Does that work if the node 0 is also conectes with the node 3? I tried but the result is now correct. If that was the case there should be 3 triangles. But by following this process I got 6

[RaoVenu]

I hate this explanation cause
a) This just explains the A^N adjacency matrix but does not give the proof / theorem behind it
b) Very formualic. Is this something that a candidate can reason about in an interview if they did not know this beforehand?

[goplay]

What to do if I want to find number of cycles in a graph?

[jcl]

you are just reading off the article, horrible explanation