[알고리즘] DFS

DFS (Depth First Search)

 

깊이우선 탐색을 예제를 통해 알아본다.

 

예제 

1 4 5 
1 2 
1 3 
1 4 
2 4 
3 4 
결과: 1 2 4 3 

 

map 상태

map[x][y]	0	1	2	3	4
0
1 (시작)			1	1	1
2		1			1
3		1			1
4		1	1	1

 

 

DFS 탐색 경로

map[x][y]	0	1	2	3	4
0
1 (시작)			1 (2 찾음)
2 (두번째 탐색)					1 (4 찾음)
3 (마지막)
4 (세번째 탐색)				1 (3 찾음)

 

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

bool map[1001][1001];
bool visit[1001];
int n;	//정점개수
int m;	//간선개수
int v;	//시작정점


void input(void)
{
	scanf("%d%d%d", &n, &m, &v);
	for(int i=1; i<=m; i++)
	{
		int x = 0, y = 0;
		scanf("%d%d", &x, &y);
		map[x][y] = map[y][x] = true;
	}
}

void DFS(int s)
{
	visit[s] = true;
	for(int i=1; i<=n; i++)
	{
		if(map[s][i] == true && !visit[i])
		{
			printf("%d ", i);
			DFS(i);
		}
	}
}

int main()
{
	input();
	printf("%d ", v);
	DFS(v);
	return 0;
}