How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

Question

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:

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 representation it is stated 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

Answer 1

I got the answer to my question at Computer Science Forum of Stack Exchange. Here's the link to the answer and I am copying the same from there as posted by @Simon Weber

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.