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, 2], 1:[0], 2:[0]}`

. Here we can clearly see that the graph contains a cycle 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`