Graph - Topological Sort

<C언어로 쉽게 풀어쓴 자료구조 > 내용

 

1. 개념

아래와 같은 그래프가 있다고 하자.

위와 같은 방향 그래프에서 간선<u,v>가 있다면 정점u는 정점v를 선행한다고 한다.

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서

모든 정점을 나열하는 것을 방향 그래프의 위상 정렬이라 한다.

위의 그림에서 많은 위상 정렬이 가능한데, 몇 개만 예를 들어보자.

A,B,C,D,E,F

B,A,C,D,E,F

가 있다.

그러나, C,A,B,D,E,F는 위상 순서가 아니다.

위가 위상 순서가 아닌 이유는

간선<A,C>가 존재하기 때문에 A번 정점이 끝나야만 C번 정점을 시작할 수 있기 때문이다.

 

2. Topological Sort 알고리즘

방향 그래프를 대상으로 위상 정렬을 하기 위한 알고리즘은 간단하다.

먼저 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부속된 모든 간선을 삭제한다.

이와 같이, 진입 차수가 0인 정점의 선택과 삭제 과정을 반복해서 모든 정점이 선택과 삭제 되면 알고리즘이 종료된다.

진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 상관 없다.

이 과정에서 선택되는 정점의 순서를 위상 순서라 한다.

위의 과정 중에 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면

실행 불가능한 프로젝트가 되어 위상 정렬 알고리즘은 종료 된다.

 

아래와 같은 그래프가 있다고 하자.

[그림 1 ]

위의 그래프를 위상 정렬을 진행해보자.

 

첫 번째로, 진입 차수가 0인 정점B를 시작으로 정점B와 부속한 간선을 제거하면

아래와 같은 그림이 된다.

두 번째로, 정점E의 진입 차수가 0이 되므로, 후보 정점은 A와 E가 된다.

정점을 E로 택하고, 정점E와 부속한 간선을 제거하자. 그러면 아래의 그림이 된다.

 

세 번째로, 진입 차수가 0인 정점은 오로지 정점A밖에 없다.

정점A를 선택하고, 정점A와 부속한 간선을 제거하자.

제거하면 아래의 그림과 같다.

네 번째로, 진입 차수가 0인 정점은 C이다.

정점C를 선택하고, 정점C와 부속한 간선을 제거하자.

제거하면 아래의 그림이 된다.

다섯 번째로, 진입 차수가 0인 정점인 D이다.

정점D를 선택하고, 정점D와 부속한 간선을 제거하자.

제거하면 아래의 그림이 된다.

결과적으로 위상순서는 다음과 같이 된다.

아래의 그래프 위상 정렬 알고리즘의 의사코드를 보자.

프로그램의 구현에 앞서 한가지 필요한 변수가 있다.

먼저 InDegree라는 1차원 배열이 하나 필요하다.

이 배열의 용도는 각 정점의 진입 차수를 기록하기 위한 용도이다.

InDegree[i]는 정점i로 들어오는 간선의 개수이다.

정점i는 InDegree[i]의 값이 0일 경우에 후보 정점이 된다.

알고리즘이 진행되면, 진입 차수가 0인 정점이 그래프에서 제거되면

그 정점에 인접한 정점의 InDegree[i]는 1만큼 감소하게 된다.

예를 들어서 다음과 같이 InDegree배열이 있다고 가정하자.

InDegree배열은 위의 [그림 2]의 그래프를 참조로 얻어온 것이다. 

위의 배열에서 진입 차수가 0인 정점은 A,B이다. 즉, A와 B가 후보 정점이 된다.

이 후보 정점들을 어딘가에 저장을 해야 하는데, 여기서는 자료구조 스택을 이용한다.

즉, 스택에 후보 정점들을 스택에 저장한다. 여기서는 A와 B가 스택에 저장이 된다.

다음 단계에서 스택에서 하나의 정점을 꺼내어 출력하고 그 정점에 인접해있는 정점들의

InDegree배열의 값을 감소시킨다.

만약 정점B를 스택에서 꺼냈다면, InDegree배열은 다음과 같이 된다.

위의 배열에서 정점E의 진입 차수값이 0이 되어 후보 정점이 되므로

정점E를 스택에 새롭게 추가한다.

 

위의 과정은 전체 정점이 출력이 될 때까지 계속된다.

만약 전체 정점이 출력되지 못하면 그래프에 사이클 등이 존재하여 위상 정렬 순서가 존재하지

않는 것이다.

 

3. 프로그램 구현

자료구조 스택이 필요하므로, 앞에서 만든 스택을 그대로 가지고 온다.

< Graph.h >

< Graph.c >

위상 정렬에서는 방향 그래프이다.

 

 

< main.c >

프로그램 실행결과

 

4. 헤더 파일 & 소스 파일

common.h

0.00MB

Graph.c

0.00MB

Graph.h

0.00MB

main.c

0.00MB

MyStack.c

0.00MB

MyStack.h

0.00MB