DFS 및 BFS를 사용한 그래프의 토폴로지 정렬 GeeksForGeeks

토폴로지 정렬:u와 v의 가장자리가 있는 경우 u가 순서에서 v 앞에 와야 하는 그래프 노드의 선형 순서입니다.

메모:

토폴로지 정렬은 유향 그래프에만 적용할 수 있습니다.

유향 그래프에 주기가 있으면 위상 정렬을 사용할 수 없습니다. 토폴로지 정렬의 정의를 만족하지 않기 때문입니다.

DFS 접근 방식:
시간 복잡도: O(N+E) 및 공간 복잡도: O(N)+O(N)+O(N)+O(N) = O(N)*4 (재귀 호출을 위한 보조 스택 공간, 방문 배열을 위한 N, 결과 배열의 경우 N, 스택의 경우 4번째 N)

/*Complete the function below*/

/*Topological sorting: 
 * A linear ordering of vertices such that if there is an edge between u->v, then 
 u appears before v in the ordering
 */
class Solution
{
    //Function to return list containing vertices in Topological order. 
    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        //we will use depth first search for this
        //we have to make sure that u appears before v , if there is 
        //an edge between u and v
        //hence using depth first search would be a better approach.
        Stack<Integer> stack = new Stack<>();
        int visited[] = new int[V];
        for(int i =0;i<V;i++){
            if(visited[i] ==0){
                dfs(i,visited,stack,adj);
            }
        }
        int result[] = new int[V];
        int index =0;
        while(!stack.isEmpty()){
            result[index] = stack.pop();
            index++;
        }
        return result;
    }
    public static void dfs(int node, int[] visited,Stack<Integer> stack, ArrayList<ArrayList<Integer>> adj){
        visited[node] = 1;
        for(Integer i: adj.get(node)){
            if(visited[i] ==0){
                dfs(i,visited,stack,adj);
            }
        }
        stack.push(node);
    }
}

토폴로지 정렬에 대한 BFS 접근: Kahn의 알고리즘 사용
시간 복잡도: O(N+E) 및 공간 복잡도는 inodegree 배열, 대기열 및 결과 배열에 대해 O(n)*3이 됩니다.

/*Complete the function below*/


class Solution
{ 

    //Function to return list containing vertices in Topological order. 
    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        //we will use Kahn's algorithm for getting topological sorting, it uses 
        //breadh first search algorithm
        // we will be required to calculate the indegree of all the nodes;
        int indegree[] = new int[V];
        /// calculating indegrees of all the nodes
        for(int i =0;i<V;i++){
            for(Integer j : adj.get(i)){
                indegree[j]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();
        //putting those nodes in the queue whose indegrees are 0
        //because these are the nodes that have no incoming edge to them hence they 
        //can be at the start of the topological sorting as it will not cause any issue
        //because we are maintaining order of u followed by v where u->v (u has edge directed towards v)
        for(int i =0;i<V;i++){
            if(indegree[i]==0){
                 q.add(i);
            }
        }
        int result[] = new int[V];
        int index =0;
        while(!q.isEmpty()){
            Integer i = q.remove();
            result[index++] = i;
            for(Integer  node : adj.get(i)){
                // here we re reducing the indegrees as the nodes that are alredy there 
                // the queue are getting removed hence there edges with the node 'node' will
                //also be removed hence there indegrees will decrease by one
                indegree[node]--;
                //and as soon as there indegrees becomes 0 means they are independent now and they have no incoming edge to them 
                //hence they can be added to queue just like we did earlier.
                if(indegree[node]==0){
                    q.add(node);
                }
            }
        }
        return result;

    }

}