[위상정렬]

위상 정렬이란::

사이클이 존재하지 않는 방향 그래프에서 간선의 방향을 거스르지 않는 순서로 정점들을 정렬하는 알고리즘을 의미한다.

 

 

구현::

그래프 데이터를 입력 받을 때 각 정점에 대한 진입간선의 수를 별도로 저장해 놓는다.

 

루프를 돌며 

ㄱ. 현재 진입 간선의 수가 0개인 정점을 찾는다.

ㄴ. 해당 정점에 연결된 정점들의 진입 간선 수를 1 내리고 해당 정점을 방문 불가 상태로 바꾼다.

 

위의 과정을 반복하며 정점을 방문 순서대로 찍으면 위상 정렬이 완료된다.

 

for(i=1;i<=e;i++) {
    cin >> s;
    cin >> e;
    arr[s][++arr[s][0]] = e;
    enterdg[e]++; 진입간선 카운트
}

for(i=1;i<=v;i++) {
    for(j=1;j<=v;j++) {
        if(enterdg[j] == 0) {
            mp = j;
            enterdg[j] = -1; 진입간선이 0인 정점찾기, -1은 방문 불가상태로 만들기
            break;
        }
    }
    cout << mp;
    for(j=1;j<=arr[mp][0];j++) {
        enterdg[arr[mp][j]]--; 해당 정점에 연결되어있는 정점들 진입간선 -1
    }
}