교과이수제도 선수과목이 있는 과목이 예다
프로그래밍 1 들어아야 2를 배울 수 있고 이러한 관계를 고려한 과목 배치에서 듣고 싶은 과목을 듣기 위해 어떤 수업을 순서대로 들어야할까.
위상 정렬(Topological sort) : 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬
사이클이 존재하면 위상정렬 불가, 선후관계 모순이 생긴다.
싸이클이 존재하지 않는 그래프를 DAG (Directed Acyclic Graph)라고 줄여서 부른다.
구현의 편의를 위한 성질
1. 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree 값만 1감소 시켜도 과정을 수행 가능
2. degree 가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가.
위상 정렬 알고리즘
1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채움
2. Indegree가 0인 정점들을 모두 큐에 넣음
3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴 이 떄 indegree가 0이 되었다면 그 정점으 ㄹ큐에 추가
5. 큐가 빌 때 까지 3, 4 번 과정을 반복
댓글