자료구조 :: 그래프(8) 위상 정렬

# 위상 정렬(topological sort)

위상정렬이란 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을
말한다. 방향 그래프를 대상으로 위상 정렬을 하기 위한 알고리즘으로는 먼저 진입 차수가 0인 정점을 선택하고,
선택된 정점과 여기에 부착된 모든 간선을 삭제한다. 이와 같이 진입 차수 0인 정점의 선택과 삭제 과정을 반복
해서 모든 정점이 선택/삭제 되면 알고리즘이 종료된다. 진입 차수 0인 정점이 여러개 존재할 경우 어느 정점을
선택해도 무방하다. 이 과정에서 선택되는 정점의 순서를 위상순서(topological order)라고 한다.
위의 과정 중에 그래프에 남아 있는 정점 중에 진입 차수 0인 정점이 없다면 위상 정렬 알고리즘은 실패한다.

책 소스는 너무 많은걸 표현 하는것같아서 좀 힘들다, 인접리스트에.. 스택에..구조체에.. 잡함수선언부가 더길다.
다음부턴 간단하게 해야지.

topologicalSort.cpp

#include <stdio.h> 
#include <stdlib.h> 

#define MAX_VERTEX 10
#define MAX_STACK_SIZE 1000

typedefstruct GraphNode{ 
int vertex; 
    GraphNode *link; 
}GraphNode; 

typedefstruct GraphType{ 
int n; 
    GraphNode *adj_list[MAX_VERTEX]; 
}GraphType; 

typedefstruct { 
int stack[MAX_STACK_SIZE]; 
int top; 
} StackType; 

void InitGraph(GraphType *g) 
{ 
int i=0; 

for(i=0;i<MAX_VERTEX;i++) 
        g->adj_list[i]=NULL; 
    g->n=0; 
} 

void InsertVertex(GraphType *g,int v) 
{ 
if( (g->n)+1 > MAX_VERTEX) 
    { 
        printf("정점 추가 실패\n"); 
        exit(-1); 
    } 
    g->n++; 
} 

void InsertEdge(GraphType *g,int u,int v) 
{ 
if(u >= g->n || v >= g->n) 
    { 
        printf("정점 번호 오류\n"); 
        exit(-1); 
    } 

    GraphNode *node=(GraphNode*)malloc(sizeof(GraphNode)); 
if(!node) 
    { 
        printf("메모리 할당 에러\n"); 
        exit(-1); 
    } 

    node->vertex=v; 
    node->link=g->adj_list[u]; 
    g->adj_list[u]=node; 
} 

void Init(StackType *s) 
{ 
    s->top=-1;     
} 

int Is_empty(StackType *s) 
{ 
return (s->top == -1); 
} 

int Is_full(StackType *s) 
{ 
return (s->top == (MAX_STACK_SIZE-1)); 

} 
void Push(StackType *s, int item) 
{  
if( Is_full(s) ) {  
        fprintf(stderr,"스택 포화 에러\n"); 
return;           
      }  
else s->stack[++(s->top)] = item;  
} 

int Pop(StackType *s)  
{  
if( Is_empty(s) ) { 
        fprintf(stderr, "스택 공백 에러\n"); 
        exit(1);          
    } 
elsereturn s->stack[(s->top)--];  
}  

int TopoSort(GraphType *g) 
{ 
int i,u,v; 
    StackType s; 
    GraphNode *node; 

int *in_degree = (int*)malloc(sizeof(int)*g->n); 

for(i=0;i<g->n;i++) 
        in_degree[i]=0; // 배열 초기화

for(i=0;i<g->n;i++) 
    { 
        node=g->adj_list[i]; 
while(node != NULL) 
        { 
            in_degree[node->vertex]++; // 정점 i의 진입간선 갯수 
            node=node->link; 
        } 
    } 

    Init(&s); 

for(i=0;i<g->n;i++) 
    { 
if(in_degree[i] == 0) // 진입차수가 없는 정점을 스택에 저장
            Push(&s,i); 
    } 

    printf("위상 순서 : "); 
while(!Is_empty(&s)) // 처음 스택이 비었으면 위상정렬 실패
    { 
        v=Pop(&s); // 진입 차수가 없는 정점 v
        printf("%d -> ",v); 
        node = g->adj_list[v]; // 정점v의 진입차수 변경

while(node != NULL) 
        { 
            u=node->vertex; 
            in_degree[u]--;  // 진입차수 감소하고
if(in_degree[u] == 0) Push(&s,u); 
            node=node->link; // 연결된 모든 간선을 제거한다
        } 
    } 

    free(in_degree); 

return0; 
} 

int main() 
{ 
    GraphType graph; 
int i; 

    InitGraph(&graph); 

for(i=0;i<6;i++) 
        InsertVertex(&graph,i); 

    InsertEdge(&graph,0,2); /*정점 0의 인접 리스트 생성*/
    InsertEdge(&graph,0,3); 

    InsertEdge(&graph,1,3); /*정점 1의 인접 리스트 생성*/
    InsertEdge(&graph,1,4); 

    InsertEdge(&graph,2,3); /*정점 2의 인접 리스트 생성*/
    InsertEdge(&graph,2,5); 

    InsertEdge(&graph,3,5); /*정점 3의 인접 리스트 생성*/

    InsertEdge(&graph,4,5); /*정점 4의 인접 리스트 생성*/

    TopoSort(&graph); 

return0; 
}