I have a graph represented as an adjacency list. I need to find a triangle in this graph. A triangle is a triple of vertices
w, such that
(v, w) and
(u, w) are edges of the graph. The graph does not necessarily needs to be undirected.
I found the following pseudocode for solving the problem:
function contains-cycle(g): for each edge (u, v) in g: for each vertex w in g: if (v, w) is an edge and (u, w) is an edge: return true return false
Now, this pseudocode is really easy and intuitive to understand, and I implemented very fast my "contains cycle" function using my adjacency list representation of a graph that I had implemented some time ago.
Note that checking if
(v, w) is an edge in an adjacency matrix representation of a graph is a constant time operation, but not in an adjacency list, where the complexity of that operation is linear in the size of the adjacency list.
Thus, with an adjacency matrix representation of a graph, the above algorithm runs roughly in O(n3) time, since iterating through the edges requires O(|V|2) and through the vertices O(|V|) times.
On the other hand, using an adjacency list representation, the time complexity of the "contains cycle" algorithm is even worse, as far as I have understood, unless we can iterate through the edges in linear time with respect to the number of edges. We could do this, if we keep track of a list of all edges in the graph while constructing the graph, but I would like to avoid this, and try to find an alternative solution.
The following is my implementation using Python 3:
def is_an_edge(u, v): """Returns true if v is an adjacent node to u. Running time complexity: O(number of adjacent nodes to u). :type u : GraphNode :type v : GraphNode """ for w in u.get_adjacent_nodes(): if w == v: return True return False def find_triangle(g): """Returns true if there's a triangle in g. A triangle in a graph is a triple of vertices u, v and w, such that all three edges (u, v), (v, w) and (u, w) are in the graph. :type g : Graph """ for u in g.get_nodes(): for v in u.get_adjacent_nodes(): for w in g.get_nodes(): if is_an_edge(v, w) and is_an_edge(u, w): return True return False
First of all, is my algorithm correct?
Its time complexity should be roughly O(n4), which is very high for a simple idea, algorithm.
Is there a better way to do what I want to achieve without keeping track of all edges of the graph?