비순환 방향 그래프 DAG (Directed Acyclic Graph)
사이클이 없는 방향 그래프
위상 정렬(Topological sort)
모든 간선(u,v)에 대해 먼저 오는 정점 순서로 정렬이 된다. (u가 v보다 먼저 오면 u->v)
그래프가 DAG인 경우만 가능한데 그 이유는 그래프에 사이클이 있으면 u가 먼저인지 v가 먼저인지 알 수 없기 때문이다.
대표적인 예로 대학교 선수과목이 있다.
위 그림을 보면 하나의 DAG에서 하나 이상의 위상정렬 결과가 나올 수 있으며, 왼쪽에서 오른쪽으로 향하는 단방향이다.
구현은 BFS(in-degree), DFS 둘 다 가능하다.
* 참고
- 진입차수 (Indegree) : 특정 노드로 들어오는 간선의 개수
- 진출차수 (Outdegree) : 특정 노드에서 나가는 간선의 개수
진행 순서 (BFS)
- Indegree가 0인 모든 노드를 큐에 넣는다. (시작하는 노드로 선수과목의 제일 첫 번째 과목이라고 생각하면 된다)
- 큐가 빌 때까지 아래 과정을 반복한다.
- 큐에서 노드를 하나 꺼내고 해당 노드에서 나가는 간선을 그래프에서 제거한다. (각 노드의 Indegree 값을 1씩 뺀다.)
- 나가는 간선에 속한 노드들 중 Indegree 값이 0이 된 노드를 큐에 삽입한다.
-> Queue에 들어온 Node의 순서가 위상 정렬을 수행한 결과이다.
1. In-degree가 0인 모든 노드를 큐에 넣는다.
아래 그림에서는 1이 삽입된다.
2. Queue에서 노드1을 꺼낸 뒤 노드1에서 나가는 간선을 제거한다.
제거한 결과 새롭게 In-degree가 0이 된 노드들을 큐에 삽입한다.
3. 큐가 빌 때까지 2번 과정을 반복한다.
[위상 정렬 결과]
- Queue에 삽입된 노드 순서: 1 → 2 → 5 → 3 → 6 → 4 → 7
참고로, 위에서 한 DAG에서 위상 정렬은 여러개가 나올 수 있다고 했는데
그 이유는 아래 예시에서 1 다음에 2와 5중 뭘 먼저 넣을지는 상관이 없어서 뭘 먼저 넣냐에 따라 위상 정렬이 약간은 달라진다.
진행 순서 (DFS)
in_degree를 확인할 필요 없이 재귀나 Stack을 사용하며 방문 표시가 필요하다.
DFS를 사용하면 Queue와 달리 진행의 역순이 위상정렬된 결과이다.
아래 표를 확인해보자
| Stack | pop | |
| A | A | |
| C B | B | |
| C D | D | |
| C F | F | 종료! |
| C | C | |
| E | E | 종료! |
[위상 정렬 결과]
- Stack에 pop 노드 순서: A → B → D → F → C → E
(틀렸다면 알려주세요)
시간 복잡도 (Time Complexity)
V: 정점의 수(Node의 수)
E : 간선의 수
- 인접 리스트 사용 O(V+E)
- 인접 행렬 사용 O(V^2)
* 참고
- 인접 리스트 : 그래프의 각 정점에 인접한 정점들을 Linked List로 만든 것이다.
그래프의 모든 간선을 조회하려면 모든 정점의 헤더부터 탐색해야 하므로 O(V+E)의 시간복잡도를 가진다.
- 인접 행렬 : 그래프의 정점을 2차원 배열로 만든 것이다.
두 정점을 연결하는 간선을 조회할 때 시간복잡도는 O(1)이다.
하지만 모든 간선의 수나 모든 간선을 조회하기 위해서는 배열 전체를 확인해야 하므로 시간복잡도는 O(V^2)이다.
여기까지 이해했다면 위상정렬 관련 알고리즘 문제를 하나 풀어보는걸 추천한다.
[백준] 2252 줄 세우기 풀이 Java, 위상 정렬
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞
sunrise-min.tistory.com
References
https://freedeveloper.tistory.com/278?category=888096
'알고리즘' 카테고리의 다른 글
| [백준] 2637 장난감 조립 풀이 Java, 위상 정렬 (0) | 2022.07.18 |
|---|---|
| [백준] 2252 줄 세우기 풀이 Java, 위상 정렬 (0) | 2022.07.17 |
| [HackerRank]Fraudulent Activity Notifications(Sort) 풀이 Java (0) | 2022.07.17 |
| Tree: Height of a Binary Tree 풀이 Java (Binary Tree 높이 구하기) (0) | 2022.07.15 |
| [백준] 15681 트리와 쿼리 풀이 Java (0) | 2022.07.15 |
댓글