7. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

너비 우선 탐색 (Breadth First Search)

 

탐색 시 너비를 우선으로 탐색 수행 (가까운 것 먼저 탐색)

= 출발 노드에서 거리 1인 것부터 탐색하게 됨.

 

- 큐와 그래프로 구현

- 맹목적인 탐색 하고자 할 때 사용

- 최단 경로를 찾아줌 (ex. 미로)

 

알고리즘 구성:

1) 시작 노드를 큐에 넣어줌 & 방문 처리

2) 알고리즘 따름 (반복문)

1) 큐에서 노드 꺼내서 방문 처리

2) 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드 큐에 넣어줌.

 

코드:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int num = 7;
int visited[7];

vector<int> a[8]; // 배열

void bfs(int start){
	queue<int> q;
	q.push(start);
	visited[start] = true; //시작점 방문 표시 
	while(!q.empty()){
		int x =q.front(); // 시작점부터 가까운 노드 찾아 넣기 
		q.pop();
		printf("%d ", x);
		for(int i = 0; i<a[x].size(); i++){ 
			// 벡터에 노드에 연결된 애들 확인 
			int y = a[x][i];
			if(!visited[y]){
				// 방문 아직 안했으면 큐에 넣어줌
				q.push(y); 
				visited[y] = true; // 그리고 방문 표시 
			}
		
		}
	}	
} 


int main(void){
	
	//한 간선마다 두개의 push_back이 일어난다 생각 
	a[1].push_back(2);
	a[1].push_back(3);
	
	a[2].push_back(1);
	a[2].push_back(4);
	a[2].push_back(5);
	
	a[3].push_back(1);
	a[3].push_back(6);
	a[3].push_back(7);
	
	a[4].push_back(2);
	a[4].push_back(5);

	a[5].push_back(2);
	a[5].push_back(4);
	
	a[6].push_back(3);
	a[6].push_back(7);
	
	a[7].push_back(3);
	a[7].push_back(6);	
	
	bfs(1);
	
	return 0;
}

이걸 응용한 알고리즘이 많아서 유용

그냥 자체로 사용할 일이 많지는 않다!

 

 

Depth First Search

- 스택을 사용함 (+ 스택을 사용하지 않아도 구현 가능: bc 컴퓨터가 기본적으로 스택원리를 사용하기 때문)

- 맹목적으로 각 노드를 탐색할 때 (모든 경우의 수를 탐색할 때)

 

1. 시작 노드를 스택에 넣고, 방문처리를 한다.

2. 반복

- 스택의 최상단 노드 확인

- 최상단 노드의 인접 노드 중 방문되지 않은 것이 있다면 스택에 넣고 방문처리, 모두 방문되었다면 스택에서 뺌

 

코드:

#include <iostream>
#include <vector>

using namespace std; 

int num = 7; // number of nodes
int visited[7];
vector <int> a[8];

void dfs(int x){
	// use recursion -> need not use stack
	if(visited[x]){
		return;
	}	
	visited[x] = true;
	cout << x << ' ';
	for(int i=0; i < a[x].size(); i++){
		int y = a[x][i];
		dfs(y);
	}
}

int main(void){
	
	//한 간선마다 두개의 push_back이 일어난다 생각 
	a[1].push_back(2);
	a[1].push_back(3);
	
	a[2].push_back(1);
	a[2].push_back(4);
	a[2].push_back(5);
	
	a[3].push_back(1);
	a[3].push_back(6);
	a[3].push_back(7);
	
	a[4].push_back(2);
	a[4].push_back(5);

	a[5].push_back(2);
	a[5].push_back(4);
	
	a[6].push_back(3);
	a[6].push_back(7);
	
	a[7].push_back(3);
	a[7].push_back(6);	
	
	dfs(1);
}