알고리즘 - DFS(Depth-First Search) 깊이 우선 탐색 소스 코드

| 문제

방향성 그래프 G에서 모든 간선들의 타입을 출력해내는 DFS(깊이 우선 탐색)을 구현하여라. DFS 과정을 진행하는 동안, 작은 숫자의 꼭짓점부터 방문하도록 설계하라. 

입력(표준 입력)

첫 번째 줄에, 꼭짓점의 개수 N을 입력한다.

두번 째 줄부터, 그래프 G의 인접 리스트가 x,y 두 정수로 표현이 된다. 이것은 x로 출발해서 y로 도착하는 간선이 있음을 의미한다.

출력(표준 출력)

G의 각각의 간선 타입들과 함께 간선들을 출력해내라. 간선들의 타입 표현은 다음과 같다.

1: 트리 엣지

2: 백 엣지

3: 포워드 엣지

4: 크로스 엣지

각각의 줄에는 세 개의 정수 x,y,z가 출력되어야 한다. 이것들은 x에서 출발하여 y로 도착하는 간선이 있으며 그 간선이 z의 타입을 가진다는 것을 의미한다.

입력	출력
6 1 2 1 4 2 5 3 5 3 6 4 2 5 4 6 6	1 2 1 1 4 3 2 5 1 3 5 4 3 6 1 4 2 2 5 4 1 6 6 2

| 소스 코드

#include <stdio.h>
#include <stdlib.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

unsigned int time = 0;
unsigned int numV = 0;

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

// 구조체 멤버 중 자기 구조체를 타입으로 하는 포인터 next을 사용하는 이유는,
// 리스트 형태로 연결하고자 하기 위함.
typedef struct _edge
{
	int toV;
	int type;
	struct _edge * next;
} Edge;

// 각 Vertxt 마다 Adjacency list 구조체가 하나씩 배당되는 것으로 생각
Vertex SetV[1000];
Edge * adjlist[1000]={NULL,};

void addEdge(int fromV, int toV)
{
	Edge * newEdge;
	Edge * temp;
	temp = adjlist[fromV];

	newEdge = (Edge*)malloc(sizeof(Edge));
	newEdge->toV = toV;
	newEdge->next = NULL;

	if(adjlist[fromV] == NULL)
	{
		adjlist[fromV] = newEdge;
	}
	else
	{
		while(temp->next != NULL)
		{
			temp = temp->next;
		}
		temp->next = newEdge;
	}
}

void DFS_Visit(int fromV)
{
	Edge * edge_fromV;
	edge_fromV = adjlist[fromV];

	time ++;
	/* DISCOVERY */
	SetV[fromV].color = GRAY;
	SetV[fromV].d = time;

	while(edge_fromV != NULL)
	{
		int toV;
		toV = edge_fromV->toV;

		switch(SetV[toV].color)
		{
		case WHITE:
			edge_fromV->type = TREE_EDGE;		// 1
			SetV[toV].pred = fromV;
			DFS_Visit(toV);
			break;

		case GRAY:
			edge_fromV->type = BACK_EDGE;		// 2
			break;

		case BLACK:
			if(SetV[fromV].d < SetV[toV].d)
				edge_fromV->type = FORWARD_EDGE;// 3
			else if(SetV[fromV].d > SetV[toV].d)
				edge_fromV->type = CROSS_EDGE;	// 4
			break;

		default:
			break;
		}

		edge_fromV = edge_fromV->next;
	}

	/* FINISHED */
	SetV[fromV].color = BLACK;
	time ++;
	SetV[fromV].f = time;
}

void DFS(void)
{
	int i;
	for(i=1; i<=numV; i++)
	{
		SetV[i].color = WHITE;
		SetV[i].pred = NULL;
	}
	time = 0;
	for(i=1; i<=numV; i++)
	{
		if(SetV[i].color == WHITE)
		{
			DFS_Visit(i);
		}
	}
}

int main(void)
{
	int i=0;
	int fromV, toV;
	Edge * temp;

	scanf("%d", &numV);
	while(scanf("%d %d", &fromV, &toV) != EOF)
	{
		addEdge(fromV, toV);
	}

	DFS();

	for(i=1; i<=numV; i++)
	{
		temp = adjlist[i];
		while(temp != NULL)
		{
			printf("%d %d %d \n", i, temp->toV, temp->type);
			temp = temp->next;
		}
	}
	return 0;
}