위상 정렬 솔루션

[1. 개요]

사이클이 없는 연결 그래프에서 위상 정렬이 가능하다.

• Cycle 이 있다면 위상 정렬을 할 수 없다.

DFS 로 구현하는 방법과 BFS 로 구현하는 방법이 있지만,

보통 BFS 로 구현하는 편이 좀 더 쉬운 것 같음 

• BFS 방식의 위상 정렬 구현 패턴을 정하도록 한다.

구현 상 그 차이점을 단순하게 정리하면 아래와 같다.

 

DFS 로 구현

• DFS 이므로 재귀로 구현
• 가장 먼저 방문 하는 것이 제일 첫번째로 해야 할 작업이며,
• 가장 마지막에 방문하는 것이 마지막으로 해야 할 작업이라 볼 수 있음
• 방문 순서는 vector 에 push_back() 으로 저장 시, vector 를 reverse 해야 함
  => 혹은 reverse iterator 를 통해.

BFS 로 구현

• 재귀로 구현 할 필요 없음
• 노드 u 의 incoming edge 개수를 파악 할 자료구조가 필요.
• 좀 더 복잡한 조건을 작성하기에 DFS 보다 유리하다 생각함.
• incoming edge 가 0 인 경우에서 빼는 경우를 만들지 않도록 할 것.
• incoming edge 개수를 빼고 나면 항상 0 이 되는지 확인 할 것.
• 0이 되면 다음에 진행 할 작업이 되는 것이므로,,

문제에서 동시에 작업을 진행한다고 명시되어 있는 경우

1. 각 작업이 끝나는 시점을 파악 하고,
   => 순차적인 코드 작성이 가능..
2. 전체 작업 중 가장 마지막에 끝나는 작업에 대한 처리를 한다.

---

[2. 예제

• https://testkernelv2.tistory.com/495
• https://testkernelv2.tistory.com/588
• c
• d
• e
• f