11-1 위상 정렬

1. 위상 정렬

① 비순환 방향 그래프 (공정이랑 비슷하네)

  - 방향 그래프이면서 사이클이 없는 그래프

② 위상 정렬

 

  - 처리해야 할 여러가지 일들이 있고, 이들 사이의 선후 관계가 있으면 이를 유향 그래프로 표현 가능

  - 유향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

  - 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있음

  - 위상 정렬은 사이클이 있어서는 안됨

  - 위상 정렬 알고리즘이란? 순서가 정해져있는 작업을 차례로 수행해야 할 때

                                             그 순서를 결정해주기 위해 사용하는 알고리즘

  - ex) 대학의 선수과목 => 각 업무를 수행하기 위한 순서를 제공!

  - 조건 : 사이클이 없는 유향 그래프

  - 진입 간선 : 유향 그래프에서 한 정점으로 들어오는 간선

  - 진출 간선 : 유향 그래프에서 한 정점에서 나가는 간선

2. 위상 정렬 알고리즘

① 위상 정렬 알고리즘 1의 작동 예

  - 진입 간선이 없는 정점은 냄비에 물 붓기와 라면봉지 뜯기

  - 이 중 임의의 냄비에 물 붓기를 선택하고 이 정점과 진출 간선을 모두 제거

  - 이제 점화와 라면봉지 뜯기가 진입 간선이 없음

  - 점화 선택 후 정점과 진출 간선 제거 -> 진입간선이 없는 정점은 라면 봉지 뜯기

  - 라면봉지 뜯기를 선택하고 이 정점과 진출 간선 모두 제거 -> 진입 간선이 없는 정점은 라면 넣기와 수프 넣기

  - 리면 넣기 선택하고 이 정점과 진출간선 모두 제거 -> 진입 간선이 없는 정점은 수프 넣기.

  - 스프 넣기-> 이 정점과 진출 간선 모두 제거 -> 계란 풀어넣기 하나 남고, 진입간선 X 

 

  - 정점이 제거되는 순서가 하나의 위상 정렬을 이룸

 

3. 위상 정렬 알고리즘의 적용 

① 위상 정렬 알고리즘2

  - 깊이 우선 탐색(DFS)을 이용한 알고리즘이며 1보다 더 많이 쓰임.

  - DFS를 거의 그래도 이용하면서 약간의 요수만 더 추가되어 알고리즘2가 더 구현하기 간단.

  - DFS와 다른 점은 함수의 맨 끝에 작업이 끝난 정점을 연결 리스트로 관리하는 부

 

② 위상 정렬 알고리즘 2의 작동 예

  - DFS-TS를 위해 아무 정점이나 선택

  - 수프 넣기를 시작 정점으로 하여 DFS-TS를 시작

  - 계란 풀어넣기 방문 => 여기서 할 일 더 없으므로 완료 => 연결 리스트에 계란 풀어넣기 삽입

  - 스프넣기 정점으로 되돌아옴(백트래킹) => 스프넣기에도 할 일 더 없으므로 연결리스트에 삽입 

  - 스프 넣기 시작 정점으로 한 DFS-TS 종료

  - 방문하지 않은 정점 중 하나를 임의로 선택하여 DFS-TS를 다시 시작

  - 냄비에 물 붓기 정점이 시작 정점으로 선택 => 점화 방문 => 라면넣기 방문

  -  라면넣기 정점에서 더 할 일 없으므로 연결 리스트에 삽입 => 점화 연결리스트에 삽입

      => 냄비에 물 붓기 연결리스트에 삽입 => 냄비에 물붓기 정점으로 한 DFS-TS 종료

  - 남은 정점 연결리스트에 삽입하고 완료됨.

  - 최종 연결 리스트는 역순으로 저장되어 있음.

③ 작동 원리

  - 위상정렬은 숫자들을 크기순으로 정렬하는 것이 아니라 유향 그래프의 정점을 정렬함

  - 위상 정렬이 필요한 경우는 그래프에서 반드시 자신보다 선행되어야 할 일을

    다 끝내야만 작업에 들어갈 수 있는 조건 주어질 때이다.