Fastest algorithm for detecting a loop in a graph

Question

Given an undirected graph what is the best algorithm to detect if it contains a cycle or not?

A breadth first or depth first search while keeping track of visited nodes is one method, but it's O(n^2). Is there anything faster?

Answer 1

The BFS and DFS algorithm for given graph G(V,E) has time complexity of O(|V|+|E|). So as you can see it's linear dependency of input. You can perform some heuristics in case you have very specialized graph, but in general it's not so bad to use DFS for that. You can check for some information here. Anyway you have to traverse the whole graph.

Answer 2

Here's your O(V) algorithm:

def hasCycles(G, V, E): 
    if E>=V:
        return True
    else:
        # here E<V
        # perform O(E+V) = O(V) algorithm 
        ...

The ... can be performed with DFS. If you have E<V and edges are stored in a meaningful way (as a list), you can probably do O(E)+logs which would make the whole algorithm O(min(E,V))+logs.

Hope you like this answer, though a bit late!

Answer 3

Testing for the presence of a cycle in a graph G(V,E) using Depth First Search is O(|V|,|E|) if the graph is represented using an adjacency list.

It is necessary to traverse the entire graph to show there are no cycles. If you are simply interested in the presence/absence of a cycle, you can obviously finish at the point a cycle is discovered.

Answer 4

If you have a simple graph, you can calculate the cyclomatic number:

C = E − N + P

Where C is the number of cycles, E is the number of edges, N is the number of nodes and P is the number of components. If you graph is connected, it is:

C = E - N + 1