위상정렬이란 방향 그래프에서 연결되어 있는 정점을 재귀가 회귀하는 역순서로 정렬하는 것을 말한다.
(재귀의 진행의 반대는 재귀의 회귀라고 하자. 진행은 스택에 쌓는작업이고 회귀는 스택을 푸는 작업이라고하자.)
내가 이해하는 대로 쓴것이다.
우선 위상정렬은 탐색과 다르게 탐색할때의 정점을 재귀의 회기시에 반환해서 정렬하는 형태를 말한다.
탐색은 정점에서 다음 노드들 다시말에 정점과 연결된 곳을 재귀진행시에 반환 했었다.(다음노드는 다음탐색의 정점이 되어서 탐색을 진행해 나간다.)
이런위상정렬을 할시 폐쇄로가 있다면 위상정렬의 해는 없어지게된다.
위상정렬을 하기위해선 우선 폐쇄로에대한 판단을 먼저 해야한다.
폐쇄로란, 특정 정점에서 시작해서 회로를 도는중 그 정점으로 돌아오는 경우 폐쇄로로 판정된다.
폐쇄로의 판정 매커니즘은 이렇다.
첫째, i->j로의 길이 있는지
둘째, j를 이번루프에 방문했는지?(여기서 말하는 루프란 재귀가 진행중일때이다.)
두조건이 참이 된다면 폐쇄로다.
둘째조건을 만족시키기위해선 현재루프가 아닌 기존 방문지의 플래그를0과 1이 아닌 다른 수로 세팅할 필요가있다. 재귀의 회귀시에 각 정점이었던 곳의 플래그를 다른수로 셋팅을하면된다.
다음은 위상정렬의 알고리즘이다.
//위상정렬
#include <stdio.h>
#define N 8
int visit(int i);
int a[N+1][N+1] = {{0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0},
{0,1,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0}};
int f[N+1],
s[N+1];
int main(int argc, char *argv[])
{
int i;
for (i=1;i<=N;i++)
if (f[i]==0)
visit(i);
for (i=N;i>=1;i--)
printf("%d " ,s[i] );
}
int visit(int i) {
int j;
int static sp=1;
f[i]=1;
for (j=1;j<=N;j++){
if (a[i][j]==1 && f[j]==0){
visit(j);
if (a[i][j]==1 && f[j]==1)
;
}
}
f[i]=2; //재귀의 회귀시 플래그의 설정
s[sp++]=i;
}
위에 부분에서 i와 j만 바꾸면 전위 행렬이다. 전위행렬은 그래프의 화살표를 반대로 한 그래프를 나타낸다.
다른부분의 i,j는 바꾸지말고 위에 남색처리한곳만 바꾸면된다.