Graph Its Implementation And Some popular BFS/DFS Problems: https://leetcode.com/discuss/study-guide/3903992/graph-its-implementation-and-some-popular-bfsdfs-problems

Topological sorting is a concept in graph theory used to arrange the vertices (nodes) of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u, v), vertex u comes before vertex v in the order. In other words, it is a way to linearly order the vertices of a directed graph in such a way that all dependencies between vertices are respected.

Key characteristics of topological sorting:

1. Applicability: It is primarily used for directed acyclic graphs (DAGs). A directed graph is a collection of vertices connected by edges, where each edge has a direction (from one vertex to another), and a DAG is a directed graph with no cycles.
2. Purpose: Topological sorting is often used to schedule tasks or activities that have dependencies. For example, in project management, it can be used to determine the order in which tasks should be performed to ensure that no task is started before its prerequisites are completed.
3. Linear Order: The result of topological sorting is a linear order of the vertices, which satisfies the constraint that if there is a directed edge from vertex u to vertex v, then u comes before v in the ordering.
4. Not Unique: In many cases, there can be multiple valid topological orderings for a given DAG, as long as they respect the dependencies.
5. Acyclic Requirement: Topological sorting cannot be applied to graphs that contain cycles because it is impossible to find a linear ordering that satisfies the ordering constraints in such graphs.

Let’s solve some examples:

Example 1 & 2:
A graph may have multiple valid topological sorting solutions.

For instance:

• In the case of 6->1 (meaning task 6 must happen before task 1) and 6->5, we find that vertex 6 has no dependencies. Therefore, it occupies the first position in our solution.
• Similarly, when we consider 4->1 and 4->3, we see that vertex 4 has no dependencies, placing it in the second position.
• Vertex 5, with its dependency 5->2, follows next in the third position.
• Vertex 3, with the dependency 3->2, takes the fourth position.

Finally, vertices 2 and 1, both having no dependencies, can be placed accordingly.

Similarly for example 2 we can simply identify solution for 2nd graph…

Example 3:
To illustrate the issue with 3rd graph:

• If we consider vertex 1 first, it has a dependency on vertex 4, which in turn depends on vertex 2, which finally depends on vertex 1, completing the cycle. This circular dependency makes it impossible to determine a linear order where each vertex appears before its dependents.
• Similarly, if we consider vertex 2 first, it depends on vertex 1, which depends on vertex 4, which, in turn, depends on vertex 2, again forming a cycle.

This circular dependency creates a paradox where each vertex depends on another vertex that ultimately depends on itself. Since topological sorting relies on a linear order that respects dependencies and prohibits cycles, it cannot produce a valid topological order for graphs with cycles.

Problem Statement :

Given a Directed Acyclic Graph (DAG) with V vertices and E edges, Find any Topological Sorting of that Graph.

Algorithm for topological sort using DFS:

1. Initialize Variables:

• Create an empty stack to store the topological order.
• Create a visited array or set to keep track of visited nodes. Initially, mark all nodes as unvisited.

2. DFS Function: Define a DFS function that takes the current node as a parameter.

3. DFS Exploration: Inside the DFS function:

• Mark the current node as visited. For each unvisited adjacent node of the current node, Recursively call the DFS function on the adjacent node.
• This step allows you to explore as deeply as possible along one path in the graph.

4. Backtracking and Stack:

• After exploring all the adjacent nodes of the current node, push the current node onto the stack. This is the backtracking step that occurs when there are no more unvisited neighbors to explore.

5. Repeat for All Unvisited Nodes: Iterate through all nodes in the graph, and for each unvisited node, call the DFS function.

6. Finalize Topological Order: After the DFS calls are complete, the stack will contain the topological order. To get the correct order, reverse the order of elements in the stack.

#include <bits/stdc++.h>
using namespace std;

class Solution {
 public:
 void dfs(int node, vector<bool> &vis, vector<int> &st, vector<int> adj[]) {
        vis[node]=1;
        for(auto a:adj[node]) {
            if(!vis[a]) {
                dfs(a,vis,st,adj);
            }
        }
        st.push_back(node);
    }
    
 vector<int> topoSort(int n, vector<int> adj[]) {
     vector<bool>vis(n, false);
     vector<int>st;
     for(int i=0;i<n;i++) {
         if(!vis[i]) {
             dfs(i,vis,st,adj);
         }
     }
     reverse(st.begin(),st.end());
     return st;
 }
};

Time Complexity: O(V+E)+O(V)
Space Complexity: O(2N), O(N) for visted array and O(N) for stack.

Problem Statement :

Given a Directed Acyclic Graph (DAG) with V vertices and E edges, Find any Topological Sorting of that Graph using Kahn’s Algorithm.

Algorithm for topological sort using Kahn’s Algorithm | BFS:

1. Initialize Data Structures:

• Create an empty list or queue to store the topological order (usually called the result list).
• Create an array to store the in-degrees of all vertices in the graph. Initialize the in-degrees for all vertices to 0.

2. Calculate In-Degrees: Calculate the in-degrees of all vertices in the graph by iterating through all edges. For each edge (u, v), increment the in-degree of vertex v.

3. Initialize Queue: Add all vertices with in-degree 0 to the queue. These are the vertices that have no incoming edges.

4. Topological Sorting:

• While the queue is not empty, do the following:
• Dequeue a vertex from the front of the queue and add it to the result list.
• For each of its adjacent vertices, reduce their in-degrees by 1 since you are removing an incoming edge.
• If any of the adjacent vertices now have an in-degree of 0, enqueue them.

5. Return the Result: If the graph is a DAG, the result list contains the topological order. Otherwise, you may handle the presence of cycles as needed.

class Solution
{
 public:
 vector<int> topoSort(int n, vector<int> adj[]) 
 {
     vector<int>indegree(n, 0), ans;
     queue<int>q;
     for(int i=0;i<n;i++) {
         for(auto a:adj[i]) {
             indegree[a]++;
         }
     }
     
     for(int i=0;i<n;i++) {
         if(indegree[i]==0) {
             q.push(i);
         }
     }
     
     while(!q.empty()) {
         int node = q.front();
         ans.push_back(node);
         q.pop();
         for(auto a: adj[node]) {
             indegree[a]--;
             if(indegree[a]==0)q.push(a);
         }
     }
     
     return ans;
     
 }
};

Time Complexity: O(V+E)
Space Complexity: O(2N), O(N) for indegree and O(N) for queue.

Problem Statement Course Schedule I(Click me for Leetcode link): There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Problem Statement Course Schedule II(Click me for Leetcode link): There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Explanation:

Think of Khan’s Algorithm as a handy tool for sorting out your course schedule puzzles. Whether you’re working on “Course Schedule I” or “Course Schedule II,” both problems involve figuring out the order in which you can take courses, considering which ones depend on others.

Khan’s Algorithm checks if you can create a workable schedule without any circular loops (like taking a course that requires another you haven’t taken yet), but it also lays out the courses in the right order. It’s a bit like having a tool that both checks if your jigsaw puzzle fits together and arranges the pieces in the correct sequence.

In a nutshell, Khan’s Algorithm simplifies both the “can you do it” and “how to do it” parts all at once.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int>g[numCourses];
        for(auto a:prerequisites) {
            g[a[1]].push_back(a[0]);
        }

        vector<int>indegree(numCourses, 0), ans;
        queue<int>q;
        for(int i=0;i<numCourses;i++) {
            for(auto a:g[i]) {
                indegree[a]++;
            }
        }
     
        for(int i=0;i<numCourses;i++) {
            if(indegree[i]==0) {
                q.push(i);
            }
        }
     
        while(!q.empty()) {
            int node = q.front();
            ans.push_back(node);
            q.pop();
            for(auto a: g[node]) {
                indegree[a]--;
                if(indegree[a]==0)q.push(a);
            }
        }
     
        // you can return true in case of Course Schedule I
        if(ans.size() == numCourses) return ans;
        return {};
    }
};

Time Complexity: O(V+E)
Space Complexity: O(2N), O(N) for indegree and O(N) for queue.

Problem Statement (Click me for Leetcode link): There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Explanation:

To find the eventual safe state in a directed graph, you can use a topological sorting approach. The idea is to identify and eliminate nodes that are part of cycles, leaving only the nodes that are not part of any cycles, which are the eventual safe states.
Note: Points to remember that any node which is a part of a cycle or leads to the cycle through an incoming edge towards the cycle, cannot be a safe node. Apart from these types of nodes, every node is a safe node.

Algorithm:

1. Create a directed graph (represented as an adjacency list) from the given input that represents the relationships between different states. The graph should consist of nodes (states) and directed edges.
2. Initialize two data structures:

• in_degrees: An array to keep track of the in-degrees (number of incoming edges) for each state. Initialize it to all zeros.
• queue: A queue data structure to keep track of states with no incoming edges.

3. Populate the in_degrees array based on the incoming edges from other states in the graph.

4. Initialize the queue with states that have no incoming edges (in-degree equals zero).

5. Create an empty list result to store the eventual safe states.

6. While the queue is not empty:

• Dequeue a state from the front of the queue.
• Add the dequeued state to the result list, as it does not have incoming edges and is part of the eventual safe state.
• For each of the state's neighbors, decrement their in-degree by 1. If a neighbor's in-degree becomes zero, enqueue it.

7. Return the result set, which contains the eventual safe states.

This algorithm identifies the eventual safe states in a directed graph by focusing on states that do not have incoming edges from other states, making them part of the eventual safe state.

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<vector<int>> adj(n);
        vector<int>indegree(n,0);
        queue<int>q;
        for(int i=0;i<n;i++) {
            for(auto a:graph[i]) {
                adj[a].push_back(i);
                indegree[i]++;
            }
        }

        for(int i=0;i<n;i++) {
            if(indegree[i] == 0) {
                q.push(i);
            }
        }
        vector<bool>safe(n);
        while(!q.empty()) {
            int node = q.front();
            q.pop();
            safe[node]=true;
            for(auto a:adj[node]) {
                indegree[a]--;
                if(indegree[a] == 0) {
                    q.push(a);
                }
            }
        }

        vector<int>ans;
        for(int i=0;i<n;i++) {
            if(safe[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

Time Complexity: O(V+E)+O(N), Extra O(N) to traverse safe array.
Space Complexity: O(3N), O(N) for indegree, O(N) for queue and O(N) for safe array.