Important Graph Algorithms for Problem solving

 

Below is the important Graph Algorithms for problem solving

Algorithms

Cycle Detection Algorithm 

For Directed graph Cycle can be detected using :

1) DFS-Based Cycle Detection using color marking (visited array)
   void dfs(node):

      mark visited

      for neighbor:

         if not visited:

             dfs(neighbor)

       stack.push(node)

2) Kahn’s Algorithm :

Build the Graph → Create an adjacency list from the prerequisites array.

Compute In-Degree → Count the number of prerequisites (incoming edges) for each course.

Start BFS with Zero In-Degree Nodes → Add all courses with zero prerequisites to a queue.

Process Courses in BFS Order → Remove edges and reduce in-degrees.

Check if All Courses Were Taken → If all courses were processed, return true; otherwise, there’s a cycle.
   

// Simple idea of Kahn's:

while (queue is not empty) {

    node = queue.poll();

    for each neighbor:

        reduce in-degree

        if in-degree == 0 → add to queue

}

Example Question: https://leetcode.com/problems/course-schedule/description/

For UnDirected graph Cycle can be detected using :

1) DFS to check for back edges

2) Union Find algorithm

Example Question: https://leetcode.com/problems/redundant-connection/description/

Bridge Finding (critical connection)

A bridge (critical connection) is an edge (u, v) such that removing it increases the number of connected components.

For UnDirected graph Finding bridges:

1) Tarjan’s Algorithm (DFS-Based)

How Tarjan’s Algorithm Works?

1. DFS Traversal: Assign each node a discovery time (disc[]).
2. Track the lowest reachable ancestor (low[]) for each node.
3. Bridge Condition: If low[v] > disc[u], then edge (u, v) is a bridge.

Example Question: https://leetcode.com/problems/critical-connections-in-a-network/description/