[자료구조] 그래프 -3

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

위상정렬(Topological Sort)

• 싸이클이 없는 방향그래프(Directed Acyclic Grape, DAG)에서 정점을 선형순서(즉, 정점들을 일렬)로 나열하는 것
  

• 위상정렬 결과는 그래프의 각 간선 <u, v>에 대해 u가 v보다 반드시 앞서 나열되어야 함
  
  

• 주어진 그래프에 따라 여러 개의 위상정렬이 존재할 수 있음
  

• 일반적으로 작업(Task)들 사이에 의존관계가 존재할 때 수행 가능한 작업 순서를 도식화하는 데에 위상정렬을 사용
  
  

• 위상정렬 찾기
  
  1. 그래프에서 진입차수가 0인 정점 v로부터 시작하여 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하는 순방향 방법
     
  2. 진출차수가 0인 정점 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하여 얻은 출력 리스트를 역순으로 반들어 결과를 얻는 역방향 방법
     
     
• 순방향 방법 : 각 정점의 진입차수를 알아야 하므로 인접리스트를 각 정점으로 진입하는 정점들의 리스트로 바꾸어야
  

• 역방향 방법 : 주어진 인접리스트를 입력에 대해 변형된 DFS를 수행하여 출력 리스트를 작성한 후에 리스트를 역순으로 만들어 위상정렬 결과를 얻음
  
  

• 핵심아이디어 : DFS를 수행하며 각 정점의 v의 인접한 모든 정점들의 방문이 끝나자마자 v를 리스트에 추가한다. 리스트가 완성되면 리스트를 역순으로 만든다
  
  • “v의 인접한 모든 정점들의 방문이 끝나자마자 v를 리스트에 추가한다” = v가 추가되기 전에 v에 인접한 모든 정점들이 이미 리스트에 추가되어 있음을 뜻함
    
  • 따라서 리스트가 완성되어 이를 역순으로 만들면 위상정렬 결과를 얻음
    
    

수행시간

• 위상정렬 알고리즘의 수행시간은 DFS의 수행시간과 동일한 O(N+M)
  
• 기본적으로 DFS를 수행하며 추가로 소요되는 시간은 정점을 리스트에 저장하고, 모든 탐색이 끝나면 리스트를 역순으로 만드는 시간이므로 이는 O(N)
  
• 따라서 위상정렬 알고리즘의 수행시간은 O(N+M) + O(N) = O(N+M)
  
  

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/yZD3up52MRE