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

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
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, 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

• How do you represent the multi-edges in the adjacency list? Oct 15 '19 at 3:02
• Yes, you are right. I missed that information in my representation list. I have corrected the same in the question. Oct 15 '19 at 9:30

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.
• 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? Oct 16 '19 at 11:17