Identifying cycle in un-directed graph

This post is a note to self on how to identify cycle in undirected graph with Breadth first search and Depth first search. I will cover directed graph in a future

Cycle

In graph theory, a cycle is a path in a graph that starts and ends at the same vertex. In other words, a cycle is a closed path in a graph that does not pass through any vertex more than once, except for the starting and ending vertex which are the same.

A-----B------C
      |      |
      |      |
      E------D

In the graph above there is cycle. B->C->D->E->B

DFS

For DFS we choose a starting node, visit it, mark it as visited and call DFS on its neighbours recursively

const dfs = (node, graph, visited) => {
  visited[node] = true;
  for(const neighbour of graph[node]) {
    if (!visited[neighbour]) dfs(neighbour, graph, visited);
  }
}

Lets say I have the above graph and I want to find whether it has a cycle or not the first thing which comes to my mind is to use Depth First Search.

Visit A, mark it visited and explore neighbours. Visit B, mark it visited and explore neighbours (we won’t visit A again as its marked visited). Visit C, mark it visited and explore neighbours (we won’t visit B again as its marked visited). Visit D, mark it visited and explore neighbours (we won’t visit C again as its marked visited). Visit E, mark it visited and explore neighbours (we won’t visit D again as its marked visited).

Now neighbour of E (which is A) is already marked visited so can I say the there is cycle in graph? not so fast. lets take a look at another example first.

A-----B

In this graph I only have two nodes A and B. lets run our BFS algorithm on it. Visit A, mark it visited and explore neighbours. Visit B, mark it visited and explore neighbours.

Now when exploring the neighbours of B, we encounter A which was already visited so our DFS algorithm will return true which is wrong as there is no cycle in the graph.

So how can I modify the algorithm so that it works correctly. The answer is simple we need to track the parent of current node, and ignore the parent when exploring the neighbours. so our above algorithm becomes the following:

const dfs = (node, graph, visited, parent) => {
  visited[node] = true;
  for(const neighbour of graph[node]) {
    if (neighbour != parent && !visited[neighbour]) dfs(neighbour, graph, visited, node);
  }
}

For the initial call we can pass -1 or some other value as per the use case

Final code for detecting cycle in undirected graph using BFS

const hasCycle = (node, graph, visited, parent) => {
  visited[node] = true;
  for(const neighbour of graph[node]) {
    if (neighbour == parent) continue;
    if (visited[neighbour]) return true;
    if (dfs(neighbour, graph, visited, node)) return true;
  }
  return false;
}

BFS

For the Breadth First Approach we will reuse the concept of keeping track of parent node, so if we are visiting a node that is already visited and its not the parent node then we will return true as it means their is a cycle otherwise we will keep exploring the further neighbours.

function isCycleBFS(startingNode, graph) {
  const visited = new Set([startingNode]);
  const queue = [];
  queue.push([startingNode, -1]);

  while (queue.length > 0) {
      const [currentNode, parentNode] = queue.shift();

      for (const neighbour of graph[currentNode]) {
          if (!visited.has(neighbour)) {
              queue.push([neighbour, currentNode]);
              visited[neighbour] = true;
          }
          else if (neighbour !== parentNode) {
              return true;
          }
      }
  }

  return false;
}