2
$\begingroup$

I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation. What I did is as follows:

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.

• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.

Pseudocode:

#adjList is the adjacency list given as a dictionary
#myQueue is a double-sided queue containing node and its parent node ([Node, parNode])
#visited is a set containing visited nodes

while(myQueue):
    currNode, parNode = myQueue.pop() #dequeue operation
    visited.add(currNode) #Marking currNode as visited
    for childNode in adjList[currNode]: #Traversing through all children of currNode
        if currNode not in visited:
            myQueue.appendleft([childNode, currNode]) #Enqueue operation
        else:
            if childNode!=parNode: #Main logic for cycle detection
                print('CYCLE DETECTED')
                break

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices 0 and 1:

Graph containing cycle

Adjacency list of above graph is: adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}. Here we can clearly see that the graph contains a cycle (In the adjacency list, it is represented by the fact that 1 appears twice in the adjacency list of 0 and 0 appears twice in the adjacency list of 1) but above algorithm is not able to detect the same because when BFS will reach vertex 1, vertex 0 is already visited but vertex 0 is also the parent of vertex 1 so this cycle will go undetected.

My question is how I can modify above algorithm to detect such cases?

Edit: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex 0 to vertex 1 and another directed edge from vertex 1 to vertex 0

$\endgroup$
  • $\begingroup$ How do you represent the multi-edges in the adjacency list? $\endgroup$ – xskxzr Oct 15 at 3:02
  • $\begingroup$ Yes, you are right. I missed that information in my representation list. I have corrected the same in the question. $\endgroup$ – LDV Oct 15 at 9:30
1
$\begingroup$

If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.

Another problem I see is that your adjacency list doesn't actually contain any information that the edge is doubled.

For directed graphs, you can just completely get rid of the "parent check", as the only time that case arrives is when you have two edges going from $u$ to $v$ and vice versa.

Additionally, be careful if the graph is not connected, your BFS will not cover all of it, so you would need to start another BFS from an unvisited vertex again. This is especially important for directed graphs, as even if the graph might be connected, your BFS will probably not cover all of it.

$\endgroup$
  • $\begingroup$ I got your point for cases when we have a forest and also the problem with my representation of the adjacency list (I have corrected my adjacency list representation to show the parallel bond information). Can you elaborate on the point "For directed graphs, you can just completely get rid of the "parent check", as the only time that case arrives is when you have two edges going from u to v and vice versa." $\endgroup$ – LDV Oct 15 at 9:34
  • $\begingroup$ For directed graphs, you only look at your outgoing edges. The only way to see a vertex which you previously visited again, is by having a cycle. The issue in non-directed graphs, where you look at the edge from which you just came, doesn't come up in this case. $\endgroup$ – Simon Weber Oct 15 at 9:58
  • $\begingroup$ I tried the same approach for a directed graph. As you mentioned I didn't require to check for parent but there seems to be other problem with the BFS approach when I have a Directed Forest. For e.g. consider the directed forest with 3 nodes: adjList = {1:[3], 2:[3]}. Here suppose I start BFS from node 1 then I will visit nodes 1 and 3. And now since my BFS setup in inside a for loop (as we do for forests). when I will start another BFS at node 2 then it will try to reach 3 which is already visited so it will show a cycle when there is none. Any comments? $\endgroup$ – LDV Oct 16 at 11:17
  • $\begingroup$ One idea would be to keep a visited flag for the overall algorithm (as you currently do) and additionally keep a visited flag only for the current BFS run (which resets every time you start from a new source). Whenever you find a vertex which is already visited overall but not visited in this run yet, you can safely stop following that vertex. When you find a vertex which has been visited in this run already, it is a cycle. $\endgroup$ – Simon Weber Oct 16 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.