CODEWITHSUNDEEP
algorithmdata-structuresgraph
Mike Sweeney
Mike Sweeney

Reputation: 2046

Count triangles (cycles of length 3) in a graph

In an undirected graph with V vertices and E edges how would you count the number of triangles in O(|V||E|)? I see the algorithm here but I'm not exactly sure how that would be implemented to achieve that complexity. Here's the code presented in that post:

for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false

Would you use an adjacency list representation of the graph to traverse all edges in the outer loop and then an adjacency matrix to check for the existence of the 2 edges in the inner loop?

Also, I saw a another solution presented as O(|V||E|) which involves performing a depth-first search on the graph and when you encounter a backedge (u,v) from the vertex u you're visiting check if the grandparent of the vertex u is vertex v. If it is then you have found a triangle. Is this algorithm correct? If so, wouldn't this be O(|V|+|E|)? In the post I linked to there is a counterexample for the breadth-first search solution offered up but based on the examples I came up with it seems like the depth-first search method I outlined above works.

Upvotes: 2

Views: 5803

Answers (2)

GiridharaSPK
GiridharaSPK

Reputation: 547

This is a naive approach to count the number of cycles. We need the input in the form of an adjacency matrix.

public int countTricycles(int [][] adj){
        int n = adj.length;
        int count = 0; 
        for(int i = 0; i < n ;i++){
            for(int j = 0; j < n; j++){
                if(adj[i][j] != 0){
                    for(int k = 0; k < n; k++){
                        if(k!=i && adj[j][k] != 0 && adj[i][k] != 0 ){
                             count++;    
                        }
                    }
                }
            }
        }
        return count/6;
    }

The complexity would be O(n^3).

Upvotes: 1

O.O.
O.O.

Reputation: 868

Firstly, note that the algorithm does not so much count the number of triangles, but rather returns whether one exists at all.

For the first algorithm, the analysis becomes simple if we assume that we can do the lookup of (a, b) is an edge in constant time. (Since we loop over all vertices for all edges, and only do something with constant time we get O(|V||E|*1). ) Telling whether something is a member of a set in constant time can be done using for example a hashtable/set. We could also, as you said, do this by the use of the adjacency matrix, which we could create beforehand by looping over all the edges, not changing our total complexity.

An adjacency list representation for looping over the edges could perhaps be used, but traversing this may be O(|V|+|E|), giving us the total complexity O(|V||V| + |V||E|) which may be more than we wanted. If that is the case, we should instead loop over this first, and add all our edges to a normal collection (like a list).

For your proposed DFS algorithm, the problem is that we cannot be sure to encounter a certain edge as a backedge at the correct moment, as is illustrated by the following counterexample:

A -- B --- C -- D
      \   /     |
        E ----- F

Here if we look from A-B-C-E, and then find the backedge E-B, we correctly find the triangle; but if we instead go A-B-C-D-F-E, the backedges E-B, and E-C, do no longer satisfy our condition.

Upvotes: 5

Related Questions