[알고리즘] 위상정렬

위상정렬은 선수과목을 나타낼 때, 사용하는 알고리즘이다. Directed graph에서 사용되는 알고리즘이다. 

이런식의 선수과목이 존재할 때, 어떤 것부터 들어야할지를 알려주는 알고리즘이라고 할 수 있다. 그렇다면 해결법은 어떨까? 일단 우리는 가장먼저 시작해야하는 것을 찾아야한다. 이는 진입차수가 0인 vertex를 찾아야한다. 만약, 진입차수가 0인 vertex를 찾을 수 없다면, 이는 위상정렬이 불가능한 것이다. 

<Stack 활용법> 

1. 그래프에서 진입차수를 저장하는 inDegree[] 선언 후, 진입차수를 초기화 시켜준다. inDegree[]를 초기화 시켜줄때는, inDegree의 진입차수를 생각해야한다. 그래서 각 인접리스트를 돌면서, from->to 일 경우, 내가 들어가는 곳의 index에 1을 더 높여줘야한다. 예를 들면, 1번 정점 -> 2번 정점이라면, inDegree[2]++ 가 되어야한다는 의미이다.

2. inDegree[i]가 0인 vertex의 index를 stack에 넣어준다.

3. stack에서 하나를 pop 시키고, 이 정점에 대해서 인접 정점에 대해 inDegree 배열을 갱신해준다. stack에서 pop 시킨 것은 result 배열에 추가해준다. 그리고 pop 시켰다는 것은 graph에서 제외시킨다는 의미이다. 위의 예시에서 미적분학을 처음 push 한담에, pop 시킨다면, 미적분학은 제외되고, 이제 진입차수가 0인 것은 프밍1과 웹프이다. 이 2개를 다시 stack에 push 시킨다. 

<Queue 활용법>

1. stack 1번과 동일

2. inDegree[i] = 0 인 vertex의 index를 enqueue한다.

3. 위상정렬은 vertex가 전부 다 나와야한다. 그전에 queue가 빈다면, 사이클이 발생하여, 위상정렬이 불가능한 상태가 된 것이다. vertex의 갯수만큼 for loop를 돌면서 하나를 dequeue 한다. 이 dequeue한 vertex의 인접 정점을 조사하면서, 각 --indegree[인접 vertex] == 0 인경우를 찾는다.(위의 스택설명과 동일) 그리고 그런경우를 찾아서 enqueue해준다.

int topologySortStack(graph* pg){
    int index=0;
    //indegree 배열 초기화
    Node* w;
    ArrayStack stack;

    for(int i=0;i<NUM;i++){
        for(w=pg->fromList[i].head->next;w;w=w->next){
            //지금 vertex에서 나온 edge가 진입하는 vertex index에 ++해준다.
            inDegree[w->data]++;
        }
    }
    for(int i=0;i<NUM;i++){
        printf("%d ", inDegree[i]);
    }
    ArrayStackInit(&stack);
    // 진입차수가 0인게 들어가야하느데,,
    for(int i=0;i<NUM;i++){
        if(inDegree[i] == 0) SPush(&stack, i);
    }
    while (!SIsEmpty(&stack)) {
        int popelement = SPop(&stack);
        result[index++] = popelement;
        // 각 정점의 진입차수 변경
        for(w = pg->fromList[popelement].head;w;w=w->next){ //여기가 그래프의 키포인트 인접한 곳을 방문하라
            if(--inDegree[w->data] == 0){ //들어오는 edge를 삭제했을때 진입차수가 0이된다면
                SPush(&stack, w->data);
            }
        }
    }
    for(int i=0;i<NUM;i++){
        printf("%s -> ", subjectName[result[i]]);
    }
    if(index != 10) return TRUE;
    else return FALSE;
}

void topologySort(graph* pg){
    int index=0;
    //indegree 배열 초기화
    Node* w;
    for(int i=0;i<NUM;i++){
        for(w=pg->fromList[i].head->next;w;w=w->next){
            inDegree[w->data]++;
        }
    }
    for(int i=0;i<NUM;i++){
        printf("%d ", inDegree[i]);
    }
    printf("\n");
    //queue 선언
    queue queue;
    queueInit(&queue);
    for(int i=0;i<NUM;i++){
        if(inDegree[i] == 0){
            enqueue(&queue, i);
        }
    }
    // vertex개수많큼 해야지 위상정렬 수행됨
    for(int i=0;i<NUM;i++){
        // 다 돌기 전에 큐가 비었다면, 사이클 발생
        if(qisEmpty(&queue)){
            printf("싸이클 발생\n");
            exit(-1);
        }
        int dequeued = dequeue(&queue);
        result[index++] = dequeued;
        for(w=pg->fromList[dequeued].head->next;w;w=w->next){
            int y = w->data;
            if(--inDegree[y] == 0){
                enqueue(&queue, y);
            }
        }
    }
    for(int i=0;i<NUM;i++){
        printf("%s -> ", subjectName[result[i]]);
    }
}