Topological Sorting(위상정렬)

Topological Sorting(위상정렬) 이란

위상정렬은 유향그래프(방향그래프)의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

위상정렬을 가장 잘 설명하는 예는 선수과목의 구조를 예로 들 수 있다. 특정 수강과목에 선수과목이 있다면 그 선수과목을 먼저 수강해야 하므로 특정과목을 수강해야 할때 위상정렬을 통해 올바른 수강순서를 찾아 낼 수 있다.

Topological Sorting(위상정렬) 조건

• 사이클이 없는 유향 그래프

Topological Sorting(위상정렬)  특징

• 모든 정점을 일렬로 나열
• 정점 x에서 정점 y로 가는 간선이 있다면 x는 반드시 y보다 앞에 위치한다.
• 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다.

Topological Sorting(위상정렬) 에서의 간선의 의미

• 순방향 간선 : 순차적으로 찾아가는 간선
• 역방향간선 : 자손에서 선조로 이어지는 간선

 

Topological Sorting(위상정렬) 알고리즘

1. 큐를 활용한 위상정렬
   • 진입차수가 0인 정점을 큐에 삽입합니다. 위의 그림에서 1
   • 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.
   • 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다. 위의 그림에서 2,3
   • 큐가 empty를 만날때 까지 같은 동작을 반복합니다.
     • 이 경우 위의 그림에서는 다음과 같이 큐에 들어 갑니다.
     
2.  스택을 활용한 위상정렬
   • DFS를 이용하여 1에서 출발을 합니다.
   • 가장 마지막 위치까지 방문을 합니다.
   • 스택에 해당 번호를 쌓고 바로 위로 빠져 나옵니다.
   • 이것을 계속 반복한 후 마지막 에 스택에 쌓인 수를 출력합니다.
     • 위의 그림을 처리하는 순서를 나타냅니다.

       

       

       

위상정렬에서 사이클이 있는지 판단하기

1. 큐를 활용한 위상정렬에서 사이클이 있는지 판단하기
   • 큐에서 모든 정점을 방문하지 않았는데 큐가 비어 있다면 사이클이 발생하는 것이다.
   • 맨 처음 그림을 예를 들어 살펴 보자.

     

2. 스택을 활용한 위상정렬에서 사이클이 있는지 판단하기
   • 스택에 데이터가 없는데 방문했던 정점이라면 사이클이 발생하는 것이다.
   • 맨 처음 그림을 예를 들어 보자.

     

     

     

문제풀이

백준 2252번 줄세우기

1. 큐를 이용해 문제풀이

   1. #include <bits/stdc++.h>
      
      using namespace std;
      #define MAXN 32000
      
      vector <int> vt[MAXN+1];
      queue <int> q;
      int n,m;
      int inDegree[MAXN+1];
      
      int main()
      {
      
          cin >> n >> m;
          for(int i=0;i<m;i++)
          {
              int x,y;
              cin >> x >> y;
              vt[x].push_back(y);
              inDegree[y]++;
          }
          for(int i=1;i<=n;i++)
          {
              if(inDegree[i]==0) q.push(i);
          }
          vector <int> res;
          while(!q.empty())
          {
              int x = q.front();
              res.push_back(x);
              q.pop();
              
              for(auto i:vt[x]){ ///x에 연결된 경로이 진입차수를 하나씩 제거 한다.
                  if(--inDegree[i]==0) q.push(i);
              }
          }
      
      
          for(auto i : res){
              cout << i << " ";
          }
      
          return 0;
      }

2. 스택을 이용해 문제풀이

   1. #include <bits/stdc++.h>
      using namespace std;
      #define MAXN 32000
      
      vector <int> vt[MAXN+1];
      stack <int> st;
      int n,m,visit[MAXN+1];
      
      void dfs(int v)
      {
          if(visit[v]) return;
          visit[v] = 1;
          for(int i=0;i<vt[v].size();i++)
          {
              dfs(vt[v][i]);
          }
          st.push(v);
      }
      
      int main()
      {
          int i;
          cin >> n >> m;
          for(i=0;i<m;i++)
          {
              int x,y;
              cin >> x >> y;
              vt[x].push_back(y);
          }
          for(i=1;i<=n;i++)
          {
              if(!visit[i]) dfs(i);
          }
          while(!st.empty())
          {
              cout << st.top() << ' ';
              st.pop();
          }
          return 0;
      }