CODEWITHSUNDEEP
graph-algorithmpseudocodebreadth-first-searchcycle-detection
Turbo
Turbo

Reputation: 73

BFS cycle detection

Could someone provide a step by step pseudocode using BFS to search a cycle in a directed/undirected graph?

Can it get O(|V|+|E|) complexity?

I have seen only DFS implementation so far.

Upvotes: 2

Views: 5081

Answers (2)

clemens
clemens

Reputation: 17711

You can take a non-recursive DFS algorithm for detecting cycles in undirected graphs where you replace the stack for the nodes by a queue to get a BFS algorithm. It's straightforward:

q <- new queue // for DFS you use just a stack
append the start node of n in q
while q is not empty do
    n <- remove first element of q
    if n is visited
        output 'Hurray, I found a cycle'
    mark n as visited
    for each edge (n, m) in E do
        append m to q

Since BFS visits each node and each edge only once, you have a complexity of O(|V|+|E|).

Upvotes: 2

Dolev
Dolev

Reputation: 684

I find BFS algorithm perfect for that. Time complexity is the same.

You want something like this(Edited from Wikipedia):

Cycle-With-Breadth-First-Search(Graph g, Vertex root):

    create empty set S
    create empty queue Q      

    root.parent = null
    Q.enqueueEdges(root)                      

    while Q is not empty:

        current = Q.dequeue()

        for each node n that is adjacent to current:
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)
            else  //We found a cycle
                n.parent = current
                return n and current

I added only the else its a cycle block for the cycle detection and removed the original if reached target block for target detection. In total it's the same algorithm.

To find the exact cycle you will have to find a common ancestor for n and current. The lowest one is available in O(n) time. Than the cycle is known. ancestor to n and current. current and n are connected.

For more info about cycles and BFS read this link https://stackoverflow.com/a/4464388/6782134

Upvotes: 2

Related Questions