DFS

다음과 같이 무방향그래프(undirected graph) 데이터를 입력받아 인접리스트를 만들고 dfs 결과를 출력하는 프로그램을 작성하라.

Example

입력파일의 첫 줄은 정점(vertex) 수와 간선(edge)의 수를 나타냄, 그래프의 정점 인덱스는 0부터 시작됨

<input.txt>

8 10
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7

 

Result

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

enum {
	FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR
};

#define NAME(a) #a
#define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false)
#define CALLOC(type,data_num,ptr) do{if(!(ptr=(type*)calloc(data_num,sizeof(type)))){CATCH(MEMORY_ALLOCATION_ERROR);}}while(false)

typedef struct node* link;
typedef struct node {
	int to;
	link next;
} node;

link* graph;

void undirected_graph_in(int from, int to);

void print_graph(void);

bool* is_print;
void dfs(int vertex);
void dfs_all(void);

#define FILE_NAME "input.txt"
int vertex_num, edge_num;
int tmp_from, tmp_to;
int main(void)
{
	FILE* fp; fopen_s(&fp, FILE_NAME, "r");
	if (fp)
	{
		fscanf_s(fp, "%d %d", &vertex_num, &edge_num);
		CALLOC(link, vertex_num, graph);
		int i;
		for (i = 0;i < edge_num;i++)
		{
			fscanf_s(fp, "%d %d", &tmp_from, &tmp_to);
			undirected_graph_in(tmp_from, tmp_to);
		}

		fclose(fp);
	}
	else CATCH(FILE_OPEN_ERROR);

	print_graph();
	CALLOC(bool, vertex_num, is_print);

	dfs_all();
	return 0;
}

void undirected_graph_in(int from, int to)
{
	link tmp1; CALLOC(node, 1, tmp1);
	tmp1->to = to;
	tmp1->next = graph[from];
	graph[from] = tmp1;

	link tmp2;CALLOC(node, 1, tmp2);
	tmp2->to = from;
	tmp2->next = graph[to];
	graph[to] = tmp2;
}

void print_graph(void)
{
	printf("< Adjacency List >\n");
	int i; link tmp;
	for (i = 0;i < vertex_num;i++)
	{
		printf("graph[%d] : ", i);
		for (tmp = graph[i];tmp;tmp = tmp->next)
			printf("%3d", tmp->to);
		printf("\n");
	}
	printf("\n");
}

void dfs(int vertex)
{
	link tmp;
	printf("%3d", vertex); is_print[vertex] = true;
	for (tmp = graph[vertex]; tmp ;tmp = tmp->next)
		if (!is_print[tmp->to])
			dfs(tmp->to);
}

void dfs_all(void)
{
	printf("< DFS >\n");
	int i, j;
	for (i = 0;i < vertex_num;i++)
	{
		for (j = 0;j < vertex_num;j++) is_print[j] = false;
		printf("DFS<%d> : ", i); dfs(i);
		printf("\n");
	}
}