[C++] DFS(Depth First Search), BFS(Breath First Search) 개념

깊이 우선 탐색(Depth First Search)

루트 노드를 시작으로 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하는 탐색 방법

 

예시코드

void dfs(int x){
	if(check[x]) return;//방문한 곳인지 체크
    check[x] = true;
    for(int i = 0; i < a[x].size(); i++){
    	int nx = a[x][i];
        dfs(nx);
	}
}

장점

- 단지 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 적습니다다.

- 목표노드가 깊은 단계에 있는 경우에 빠르게 구할 수 있습니다.

​

단점

- 해가 없는 경로에 깊이 빠질 가능성이 있습니다.

- 얻어진 해가 최단 경로를 통해 얻어진다는 보장이 없습니다. (위의 이미지에서 구해야 하는 해는 2번인데 1번쪽을 전부 처리하고 2번을 왔는데 그렇게 가는 형식이 최단 경로는 아닙니다.)

 

너비 우선 탐색(Breath Firsh Search)

노드를 탐색하되, 인접한 노드들을 탐색하면서 탐색해나가는 방법

​

예시코드

void bfs(int start) {
	queue<int> q;
	q.push(start);
	check[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < a[x].size(); i++) {
			int nx = a[x][i];
			if (!check[nx]) {
				q.push(nx);
				check[nx] = true;
			}
		}
	}
}

장점

- 출발 노드에서 목표 노드까지 최단 길이 경로를 보장합니다.

​

단점

- 경로가 길 경우 탐색 가지가 급격히 증가하며 메모리 공간을 많이 필요하게 됩니다.

- 해가 존재하지 않으면 유한 그래프의 경우 모든 그래프 탐색 후 실패로 끝난다. 반대로 무한 그래프의 경우에는 해도 못찾고 안끝납니다.

 

 

DFS : 1 - 3 - 4 - 2 - 6 - 5

BFS : 1 - 3 - 2 - 4 - 6 - 5