Topological Sorting

Topological Sorting(위상정렬) 구조

각 노드에 나타낸 숫자는 자신을 향하는 노드의 갯수를 표시 한 것 입니다. 이것은 indegree라고도 불리며 indegree의 값이 0인 노드부터 시작하여 자신과 연결된 노드들의 indegree의 값을 감소 시키면서 0이 되는 노드마다 queue에 넣고를 반복합니다.

Topological Sorting 코드

초기화

cin >> n >> m;
while (m--) {
    int x, y;
    cin >> x >> y;
    cur[x].push_back(y);
    cnt[y]++;
}

노드의 갯수와 간선의 갯수를 입력 받습니다. x -> y로 향하는 노드 이므로 x의 연결노드로 y를 추가하고 y의 indegree 값을 1 증가 시킵니다.

시작 노드 추가

queue<int> temp;
for (i = 1; i <= n; i++){
	if (cnt[i] == 0){
    	temp.push(i);
    }
}

indegree가 0인 노드들을 queue에 넣어서 진행합니다.

노드 순회

while(temp.size()) {
    int here = temp.front();
    temp.pop();
    
    for (j = 0; j < cur[here].size(); j++) {
        if (--cnt[cur[here][j]] == 0) {
            if (visi[cur[here][j]] == 0) {
                t.push_back(cur[here][j]);
                visi[cur[here][j]] = 1;
            }
            temp.push(cur[here][j]);
        }
    }
}

queue에서 하나씩 꺼내면서 기준 노드를 가지고 근접노드에 접근합니다. 기준 노드에 연결된 노드들의 ingreed 값을 -1 해주면서 ingreed의 값이 0이고 visi배열를 통해 미방문인 노드에 접근 했을때 queue에 연결된 노드를 넣어주고 visi 방문 체크를 합니다.