DFS/BFS(깊이우선/너비우선 탐색) 공부

DFS - 깊이 우선 탐색

 

연결된 노드를 계속 들어가며 재귀호출한다.

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

bool visit[10] = { false };		//방문여부
vector<int> map[10];

int num;

#pragma warning(disable:4996)

void dfs(int v)
{
	//방문하지 않은것만 체크한다
	if (visit[v])
		return;
	
	visit[v] = true;
	printf("%d", v);

	for (int i = 0; i < map[v].size(); i++)
	{
		int tmp = map[v][i];
		//재귀함수로 다음으로 넘어간다.
		dfs(tmp);
	}
}

//양쪽 노드를 연결해준다
void AddLine(int a, int b)
{
	map[a].push_back(b);
	map[b].push_back(a);
}

int main(void) {
	AddLine(1, 2);
	AddLine(1, 3);
	AddLine(2, 4);
	AddLine(2, 5);
	AddLine(5, 8);
	AddLine(3, 6);
	AddLine(6, 9);
	AddLine(3, 7);

	//1번 노드로부터 BFS 탐색
	dfs(1);
 	return 0;
}

 

이렇게 만들어진 노드가 있다.1부터 시작하기로 한다.

우선 1번을 방문한다.

1번과 연결된 2번으로 타고들어간다.

연결된 노드중 1번은 이미 방문했기 때문에 return, 4번으로 방문한다

4번과 연결된 2번은 return,4번에서 더 이상의 깊이가 없으므로 해당 재귀는 끝이난다.다음 2번의 두번째 노드인 5로 방문한다.

2번은 이미 방문 했으니 갈 수 없고, 8번으로 방문한다.

8번에서 5번으로도 갈 수 없기에, 2번 파생의 재귀함수는 전부 끝이난다. 다음 1번의 두번째 노드인 3번 노드로 방문한다.

3번에서 1번으로 갈수는 없고,첫번째 노드인 6번으로 이동한다.

3번으로는 돌아갈 수 없고 9번으로 이동한다.

6번으로 돌아 갈 수 없으니 3번의 두번째 노드인 7번으로 간다

이렇게 모든 방문을 마칠 경우의 순서는 1 2 4 5 8 3 6 9 7이 된다.

 

 

BFS - 너비 우선 탐색

 

큐를 사용해서 루트 노드에 연결되어있는 모든 노드를 다 탐색한 뒤 깊이로 들어간다.

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

bool visit[10] = { false };		//방문여부
vector<int> map[10];

queue<int> q;
int num;

#pragma warning(disable:4996)

void bfs(int v)
{
	q.push(v);
	visit[v] = true;
	while (!q.empty())		//큐에 값이 없어질 때까지 반복한다
	{
		int node = q.front();
		q.pop();
		printf("%d", node);
		for (int i = 0; i < map[node].size(); i++)
		{
			int tmp = map[node][i];
			if (visit[tmp] == false)
			{
				q.push(tmp);
				visit[node] = true;
			}
		}
	}
}

//양쪽 노드를 연결해준다
void AddLine(int a, int b)
{
	map[a].push_back(b);
	map[b].push_back(a);
}

int main(void) {
	AddLine(1, 2);
	AddLine(1, 3);
	AddLine(2, 4);
	AddLine(2, 5);
	AddLine(5, 8);
	AddLine(3, 6);
	AddLine(6, 9);
	AddLine(3, 7);

	//1번 노드로부터 BFS 탐색
	bfs(1);
 	return 0;
}

BFS에서도 똑같은 노드를 기반으로 설명한다.

 

시작은 1이 큐에 들어간다.

1을 빼고, 1에 연결된 노드들을 순회해서 큐에 넣는다.

2번을 빼고 2번과 연결된 4,5를 연결한다(1은 이미 방문해서 제외)

3을 빼고. 3과 연결된 6,7을 넣는다.(1은 이미 방문해서 제외)

 

4번과 연결된건 2이지만, 이미 방문했기에 4만 배출되고 끝이다.

5를 빼고, 5와 연결된 8을 큐에 넣는다.2는 이미 방문했으므로 넣지않는다.

6을 빼고, 6과 연결된 9번을 큐에 넣는다.3은 이미 방문했으니 넣지않는다

3번은 이미 방문했으므로 7번만 뺀다.

5번은 이미 방문했으므로 8번만 뺀다

6번은 이미 방문했으므로 9번을 뺀다.

이 순서대로 빼면 1 2 3 4 5 6 7 8 9 순으로 pop된다.