DAG(Directed Acyclic Graph) = 사이클이 없는 방향 그래프.
DAG에서 선형 순서를 정렬.
예를 들면, 대학생 졸업 요건을 갖추기 위해 각 과목이 있고 선수 과목이 있다.
선수 과목을 들어야 다음 과목을 들을 수 있다.
이러한 선수 관계를 위상 정렬하면 들어야할 과목 순서를 정할 수 있다.
이론
정리 - 방향 그래프가 비순환이면, dfs는 역행 간선을 만들지 않고 그 역도 성립한다.
소스 코드
vector<int> ts; // 위상 정렬을 역순으로 저장하기 위한 변수
void dfs(int u){
dfs_num[u] = VISITED;
for(int i = 0; i < adj[u].size(); ++i){
int v = adj[u][i];
if (dfs_num[v] == UNVISITED)
dfs(v);
}
ts.push_back(u); // 기존 dfs에서 이 부분만 추가하면 됨. 방문이 끝나면서 하나씩 담음
}
칸 알고리즘
BFS를 응용함.
DFS기반 알고리즘으로 풀지 못할 경우도 있다.
그럴때 사용하면 된다.
소스 코드
// 진입 차수가 0인 정점들을 우선순위 큐에 삽입
while(!q.empty()){
int u = q.dequeue();
ts.push_back(u); // 정점 u를 위상 정렬 목록에 추가
for(int i = 0; i < adj[u].size(); ++i){
int v = adj[u][i];
in_edge[v]--; // 정점 u에 모든 진출 간선을 제거
if (in_edge[v] == 0) // 제거 하면서 u에 연결된 정점 v가 진입 차수가 0이 되면,
q.enqueue(v);
}
}
Leave A Comment