Search⌘ K
Home
Courses
Competitive Programming - Crack Your Coding Interview, C++

Cycle Detection Using Breadth-First Search

Explore how to detect cycles in undirected graphs with Breadth-First Search. Understand the BFS approach, parent node tracking, and adjacency list usage through C++ examples.

We'll cover the following...

Problem statement

You are given an undirected graph, and you need to check whether there is any cycle or not.

Solution

To solve this problem, either Breadth-First Search or Depth First Search can be used to detect cycles. In the case of a directed graph, only the Depth-First Search can be used. Let’s move on to the implementation as we have already discussed Breadth-First Search and there is only a minor difference in the solution. Let’s look at the code now.

C++
#include <iostream>
#include <map>
#include <queue>
#include <list>
using namespace std;
template <typename T>
class Graph
{
  map<T, list<T>> adjList;
  public:
  Graph()
  {
  }
  void addEdge(T u, T v, bool bidir = true)
  {
    adjList[u].push_back(v);
    if (bidir)
      adjList[v].push_back(u);
  }
  bool isCyclicBFS(T src)
  {
    map<T, bool> visited;
    map<T, int> parent;
    queue<T> q;
    q.push(src);
    visited[src] = true;
    parent[src] = src;
    while (!q.empty())
    {
      T node = q.front();
      q.pop();
      //Iterate over the neighbors of that node leaving the parent node
      for (T neighbor : adjList[node])
      {
        if (visited[neighbor] == true && parent[node] != neighbor)
          return true;
        else if (!visited[neighbor])
        {
          visited[neighbor] = true;
          parent[neighbor] = node;
          q.push(neighbor);
        }
      }
    }
    return false;
  }
};
int main()
{
  Graph<int> g;
  g.addEdge(1, 2);
  g.addEdge(1, 4);
  g.addEdge(4, 3);
  g.addEdge(2, 3);
  if (g.isCyclicBFS(1))
    cout << "Cyclic Graph";
  else
    cout << "Non cyclic";
}

Explanation:

  • From lines 1 to 4, we
...