[C#] 방향 비순환 그래프(DAG), 위상정렬

---

DAG 위상정렬

---

위상정렬

방향 비순환 그래프에서 가능한 정렬 방법입니다.
모든 간선 ( u -> v ) 가 u는 항상 v보다 앞으로 정렬

위상정렬 예시

A -> C
B -> C
C -> D

• 가능한 정렬
• A B C D
• B A C D

예시 문제

2252 줄세우기
BFS, DFS방식

BFS 방식

1. 모든 정점 진입 차수(indegree) 계산
2. 진입 차수가 0인 정점을 큐에 넣음(가장 앞쪽 순서)
3. 큐에서 하나 꺼내서 결과에 추가 -> 그 정점에서 나가는 간선 확인 차수–
4. 확인 후 진입 차수가 0이 된 정점을 큐에 넣기
5. 큐가 빌 때까지 반복

BFS 위상정렬

class Program
{
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
        int n = input[0];
        int m = input[1];

        List<int>[] graph = new List<int>[n+1];
        int[] indegree = new int[n + 1];

        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List<int>();
        }

        for (int i = 0; i < m; i++)
        {
            int[] ab = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
            int a = ab[0];
            int b = ab[1];

            graph[a].Add(b);

            //⭐1. 모든 정점 진입 차수(indegree) 계산  
            indegree[b]++;
        }

        Queue<int> que = new Queue<int>();
        for (int i = 1; i <= n; i++)
        {
            if (indegree[i]==0)
            {
                //⭐2. 진입 차수가 0인 정점을 큐에 넣음(가장 앞쪽 순서)  
                que.Enqueue(i);
            }
        }

        List<int> result = new List<int>();

        //⭐5. 큐가 빌 때까지 반복  
        while (que.Count>0)
        {
            //⭐3. 큐에서 하나 꺼내서 결과에 추가  
            int now = que.Dequeue();
            result.Add(now);

            
            foreach (int next in graph[now])
            {
                //⭐3-2. -> 그 정점에서 나가는 간선 확인, 차수--  
                indegree[next]--;
                if (indegree[next]==0)
                {
                    //⭐4. 확인 후 진입 차수가 0이 된 정점을 큐에 넣기 
                    que.Enqueue(next);
                }
            }
        }

        sw.WriteLine(string.Join(" ",result));
        sw.Flush(); sw.Close();
    }
}

DFS 방식

1. 방문하지 않은 노드에서 시작해서 DFS 진행
2. 해당 노드에서 갈 수 있는 모든 후행 노드를 DFS로 방문
3. 자식을 다 방문하고 나서 현재 노드를 스택에 push
4. 모든 노드를 처리한 뒤 스택에서 pop

DFS 위상정렬

class Program
{
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    static List<int>[] graph;
    static bool[] visited;
    static Stack<int> stack = new Stack<int>();

    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
        int n = input[0];
        int m = input[1];

        graph = new List<int>[n+1];
        visited = new bool[n + 1];

        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List<int>();
        }

        for (int i = 0; i < m; i++)
        {
            int[] ab = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
            int a = ab[0];
            int b = ab[1];

            graph[a].Add(b);
        }

        for (int i = 1; i <= n; i++)
        {
            if (!visited[i])
            {
                //⭐1. 방문하지 않은 노드에서 시작해서 DFS 진행 
                DFS(i);
            }
        }

        while (stack.Count>0)
        {
            //⭐4. 모든 노드를 처리한 뒤 스택에서 pop 
            sw.Write(stack.Pop() + " ");
        }

        sw.Flush(); sw.Close();
    }

    static void DFS(int node) 
    {
        visited[node] = true;
        foreach (int next in graph[node])
        {
            //⭐2. 해당 노드에서 갈 수 있는 모든 후행 노드를 DFS로 방문  
            if (!visited[next])
            {
                DFS(next);
            }
        }

        //⭐3. 자식을 다 방문하고 나서 현재 노드를 스택에 push  
        stack.Push(node);
    }
}

---

메모

BFS : 진입 차수 0인 노드부터 -> 큐 활용.
DFS : 후행 노드를 먼저 DFS 탐색 -> 스택 활용.

---