알고리즘 - Topological Sort (위상 정렬)

| 문제

주어진 그래프가 만약 DAG(Directed Acyclic Graph, 방향성 비사이클 그래프)라면, 그 그래프의 꼭짓점들을 위상 정렬 하는 프로그램을 구현하라. DFS(Depth-First Search, 깊이 우선 탐색) 과정을 진행하는 동안, 작은 숫자의 꼭짓점들을 먼저 방문하도록 설계해야 한다.

입력(표준 입력)

첫 번째 에는 꼭짓점의 개수를 입력한다.

다음 줄부터, 그래프 G의 인접 리스트가 서로 연결되어 있는 꼭짓점인 x와 y로 표현되어야 한다. 이 것은 꼭짓점 x에서 꼭짓점 y로 나아가는 간선이 존재함을 의미한다.

출력(표준 출력)

첫 번째 줄에는, 주어진 그래프 G가 DAG라면 1을 출력하고, 아니면 0을 출력하게 한다.

그리고 그래프가 DAG이면 그 다음 줄에, 위상 순서대로 꼭짓점들을 출력해야 한다.

example)

입력	출력
9 1 4 1 5 2 5 4 5 4 6 6 9 7 6 7 8 8 9 EOF 입력(윈도우에서는 Ctrl+Z)	1 7 8 3 2 1 4 6 9 5

| 소스 코드

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

#define WHITE			0
#define GRAY			1
#define BLACK			2

#define TREE_EDGE		1
#define BACK_EDGE		2
#define FORWARD_EDGE	3
#define CROSS_EDGE	4

#define TRUE			1
#define FALSE			0

typedef struct _vertex{
	int color;
	int f;
	int d;
} Vertex;

typedef struct _VertexInfo{
	int out_degree;
	int * list;
} VertexInfo;

Vertex * vertex;
VertexInfo * vertexInfo;
int numV, time;
int * topoList;
int topo_num=0;
int isDAG = TRUE;

void addEdge(int fromV, int toV){
	int i=0;
	int cur=0;

	for(i=0; i < numV; i++)
	{
		if(vertexInfo[fromV].list[i] == 0)
			break;
		cur ++;
	}
	vertexInfo[fromV].list[cur] = toV;
}

void DFS_Visit(int fromV){
	int i=0, toV;

	/* DISCOVERED */
	time++;
	vertex[fromV].color = GRAY;
	vertex[fromV].d = time;

	for(i=0; i < vertexInfo[fromV].out_degree; i++){
		toV = vertexInfo[fromV].list[i];
		switch(vertex[toV].color)
		{
		case WHITE:
			DFS_Visit(toV);
			break;

		case GRAY:
			isDAG = FALSE;
			break;

		case BLACK:
			break;
		default:
			break;
		}
	}

	/* FINISHED */
	vertex[fromV].color = BLACK;
	topoList[numV-(topo_num++)] = fromV;
	time ++;
	vertex[fromV].f = time;
}

void Sort(int * list, int num)
{
	int i=0, j=0, tmp;

	for(i=0; i < num; i++)
	{
		for(j=i+1; j < num; j++)
		{
			if(list[i] > list[j])
			{
				tmp = list[i];
				list[i] = list[j];
				list[j] = tmp;
			}
		}
	}
}


void DFS(void)
{
	int i;
	for(i=1; i <=numV; i++)
	{
		vertex[i].d = 0;
		vertex[i].f = 0;
		vertex[i].color = WHITE;
		Sort(vertexInfo[i].list, vertexInfo[i].out_degree);
	}

	time = 0;
	for(i=1; i <=numV; i++)
	{
		if(vertex[i].color == WHITE)
		{
			DFS_Visit(i);
		}
	}
}


int main(void)
{
	int i=0, j=0;
	int fromV, toV;

	scanf("%d", &numV);

	/* INITIALIZATION START! */
	vertexInfo = (VertexInfo*)malloc(sizeof(VertexInfo)*(numV+1));
	for(i=1; i <=numV; i++){
		vertexInfo[i].list = (int*)malloc(sizeof(int)*numV);
		vertexInfo[i].out_degree = 0;
	}
	for(i=1; i <=numV; i++){
		for(j=0; j < numV; j++){
			vertexInfo[i].list[j] = 0;
		}
	}
	vertex = (Vertex*)malloc(sizeof(Vertex)*(numV+1));
	topoList = (int*)malloc(sizeof(int)*(numV+1));
	/* INITIALIZATION END! */
	

// INPUT
	while(scanf("%d %d", &fromV, &toV)!=EOF){
		addEdge(fromV, toV);
		vertexInfo[fromV].out_degree ++;
	}
	DFS();

// OUTPUT
	printf("%d\n", isDAG);
	if(isDAG)
	{
		for(i=1; i <=numV; i++)
			printf("%d ", topoList[i]);
	}

	return 0;
}