컴퓨터공학 💻 도서관📚
위상정렬 . 3 본문
사이클이 없는 방향 그래프를 DAG 라고 한다
위상정렬 알고리즘은 DFS, 큐를 이용해서 구현할 수 있다
사이클이 존재하는 방향 그래프라면 사이클에 포함되어 있는 모든 노드는 진입 차수가 1이상이기에
지금과 같이 설계한 경우 사이클에 포함되어 있는 모든 노드는 큐에 들어갈 수 없기 때문에 위상 정렬을 수행할 수 없다
(여러 개의 노드가 한꺼번에 큐에 들어갈 때는 어떤 순서로 들어가도 상관 없지만 예제에서는
더 작은 번호의 노드가 먼저 들어가게 설정했다)
(중간 과정 생략)
C++ 코드
자바 코드
'✅🌲강의 복습 노트 > 이코테2021 알고리즘 훈련' 카테고리의 다른 글
투 포인터와 구간 합 계산법 . 2 (0) | 2024.11.28 |
---|---|
소수 판별 알고리즘 . 1 (1) | 2024.11.28 |
크루스칼 알고리즘 . 2 (0) | 2024.11.26 |
서로소 집합 자료구조 . 1 (0) | 2024.11.26 |
최단 경로 알고리즘 문제 2 . 5 (0) | 2024.11.24 |
Comments