Cycle Detection in a Directed Graph

Detect cycles in a directed graph using two different approaches:

DFS Approach: We track the nodes visited in the current recursive path using an additional data structure.
BFS Approach (Kahn's Algorithm): We check for cycles using the topological sort method. If the graph cannot be fully topologically sorted, a cycle exists.

Approach

1. DFS Cycle Detection

Visited and DFS Visited: We use two data structures to track:
- visited: If a node has been visited at least once during any DFS traversal.
- dfsVisited: If a node is currently in the recursive call stack.
Cycle Detection: A cycle exists if we encounter a node in the current path (dfsVisited) during traversal.

2. BFS Cycle Detection (Kahn's Algorithm)

Topological Sorting: A topological sort of a graph should include all nodes. If it doesn't, then some nodes couldn't be processed due to a cycle, indicating the presence of a cycle.
Indegree Calculation: We calculate the indegree of each node and start BFS traversal from nodes with indegree 0. During traversal, we reduce the indegree of each neighbor.

Code Explanation

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <list>

using namespace std;

// Function to check for a cycle using DFS
bool checkCycleDfs(int node, unordered_map<int, bool> &visited,
                   unordered_map<int, bool> &dfsVisited,
                   unordered_map<int, list<int>> &adj) {
  visited[node] = true;
  dfsVisited[node] = true;

  for (auto neighbor : adj[node]) {
    if (!visited[neighbor]) {
      if (checkCycleDfs(neighbor, visited, dfsVisited, adj)) {
        return true;
      }
    } else if (dfsVisited[neighbor]) {
      return true; // Cycle found: neighbor is already in the current DFS path
    }
  }

  dfsVisited[node] = false; // Backtrack to explore other paths
  return false;
}

// Function to do Topological sort using BFS traversal
vector<int> topoLogicalSort_BFS(unordered_map<int, list<int>> &adjList,
                                int numberOfNodes) {
  queue<int> bfsQue;
  unordered_map<int, int> indegree;
  vector<int> ans;

  // Count indegrees of each node
  for (int i = 0; i < numberOfNodes; i++) {
    for (auto it : adjList[i]) {
      indegree[it]++;
    }
  }

  // Add nodes with 0 indegrees as starting points
  for (int i = 0; i < numberOfNodes; i++) {
    if (indegree[i] == 0) {
      bfsQue.push(i);
    }
  }

  // Perform BFS traversal
  while (!bfsQue.empty()) {
    int node = bfsQue.front();
    bfsQue.pop();
    ans.push_back(node);

    for (auto nbr : adjList[node]) {
      indegree[nbr]--;
      if (indegree[nbr] == 0) {
        bfsQue.push(nbr);
      }
    }
  }
  return ans;
}

// Function to detect a cycle in a graph using both DFS and BFS
vector<bool> detectCycleInGraph(int n, vector<pair<int, int>> &edges) {
  unordered_map<int, list<int>> adj;
  unordered_map<int, bool> visited;
  unordered_map<int, bool> dfsVisited;

  bool ans_DFS = false;
  bool ans_BFS = false;

  // Create adjacency list
  for (int i = 0; i < edges.size(); i++) {
    int u = edges[i].first;
    int v = edges[i].second;
    adj[u].push_back(v);
  }

  // DFS cycle detection
  for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
      if (checkCycleDfs(i, visited, dfsVisited, adj)) {
        ans_DFS = true;
        break;
      }
    }
  }

  // BFS cycle detection
  vector<int> topoSort = topoLogicalSort_BFS(adj, n);
  if (topoSort.size() < n) {
    ans_BFS = true;
  }

  return {ans_BFS, ans_DFS};
}

int main() {
  int n = 4;
  vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 1}}; // Has a cycle

  vector<bool> hasCycle = detectCycleInGraph(n, edges);

  cout << "hasCycle (BFS) : " << hasCycle[0] << endl;
  cout << "hasCycle (DFS) : " << hasCycle[1] << endl;

  return 0;
}

Key Points:

DFS: Detects cycles by checking if a node is revisited in the current path.
BFS: Detects cycles by attempting topological sorting. If topological sorting is incomplete, a cycle exists.

Time Complexity: