DAG(Directed Acyclic Graph)
•
방향 사이클이 없는 방향 그래프
•
예시) 작업들의 우선순위
용어
•
Incoming : 들어오는 Edge
◦
Indegree : 들어오는 Edge 개수 (진입간선)
•
Outcoming : 나가는 Edge
◦
Outdegree : 나가는 Edge 개수 (진출간선)
위상 정렬(Topology Sort)
•
DAG이어야 한다. → 방향 그래프, 사이클 x
•
indegree & outdegree로 구분
•
모든 정점에 연결된 간선을 한 번씩 보게 된다. 시간 복잡도는 O(V + E)
로직
1.
정점들의 Indegree[1~N]을 계산한다. (들어오는 간선 개수) → O(E)
2.
들어오는 간선(Indegree)이 0개인 정점들을 찾아, Q에 넣는다. → O(V)
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0)
q.offer(i);
}
Java
3.
Q가 빌때까지 순회한다. → O(V + E)
a.
D에서 꺼낸 x를 "정렬"시킨다. (결과 저장하기)
b.
Graph에서 정점 x를 "제거"한다.
c.
"새롭게 정렬 가능한 점"을 찾아, Q에 넣는다.
while(!q.isEmpty()) {
int x = q.poll();
result.add(x); //3-1 정렬
for (int next : adj.get(x)) { //3-2 제거
if (--indegree[next] == 0) q.offer(next);
}
}
Java
관련 문제
•
•
_thumbnail.jpg&blockId=0704776a-0911-43ee-bf72-e191143a6458&width=512)
