BFS cycle detection

Question

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.

Why do you want to use BFS ? Do you have to ? If not, read this, you might prefer using DFS : http://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs — derOtterDieb, Jan 30 '17 at 13:13
@kazu I want to see how it is implemented because my implementation is screwed up. — Turbo, Jan 30 '17 at 13:16
Do you just need to know whether a cycle exists or do you need to extract the specific circle itself? — Codor, Jan 30 '17 at 13:17
@Codor just existence I will try to extract myself (but if you can provide that also it will be great). — Turbo, Jan 30 '17 at 13:18

clemens · Accepted Answer · 2020-11-21T15:12:47.417

2

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|).

edited Nov 21 '20 at 15:12

answered Jan 30 '17 at 13:15

clemens

16,716
11
50
65

What is a non-recursive DFS? Could you provide pseudocode? I tried implementing but could not make it work. – Turbo Jan 30 '17 at 13:16
thank you. Do we have to use queue? how do you print? – Turbo Jan 30 '17 at 13:29
Yes, for BFS you have to use a queue. Note, this is pseudo code. There is no printing. The output statement says that the algorithm has reached a special state. This _may_ be printing in a real implementation. – clemens Jan 30 '17 at 13:40
let me think about it. if i have trouble getting to print I will update. – Turbo Jan 30 '17 at 13:46
2

I don't think works. Consider a case where there are two paths to the same node. Just because you visited it before, doesn't make it a cycle. https://stackoverflow.com/a/2869661/986067 – Forethinker Aug 09 '20 at 04:44
This only words for cycle detections in undirected graphs. With directed graphs it produces false positives. – vcovo Nov 21 '20 at 13:22
1

@vcovo Yes, you're right. I'll update my description. – clemens Nov 21 '20 at 15:11

score 2 · Answer 2 · edited May 23 '17 at 12:25

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

BFS cycle detection

2 Answers2