[알고리즘]깊이우선탐색(DFS),너비우선탐색(BFS)

그래프 탐색이란?

하나의 정점에서 시작하여 다른노드와 이어진 간선을 통해 다른 모든 정점들을 한번씩 방문하는 것입니다.

깊이우선탐색, 너비우선탐색은 그래프 탐색의 기본이라고 할 수 있습니다.

 

깊이우선탐색(Depth-First Search)

새로운 노드가 탐색될 때마다 그 노드로 이동하고, 다시 돌아와서 새로운 노드를 탐색하는 방법

 

1. 시작노드에서 시작
2. 인접한 다른노드 탐색
3. 탐색한 노드에서 인접한 노드 중 탐색되지않은 노드 확인
4. 인접한 노드 중 탐색되지 않은 노드가 없으면 다시 되돌아오면서 탐색되지않은 노드 확인
5. 만약 탐색되지 않은 노드가 있다면 탐색

깊이우선탐색

소스코드(c++)

#include <iostream>
#include <vector>

using namespace std;

int N, E; //노드개수, 에지개수
int U, V; //연결되어있는 노드 U,V
int **arr = new int*[N];  //연결여부
bool *check = new bool[N]; //탐색여부

//깊이우선탐색
void dfs(int x){ 
    check[x] = true;
	cout<<x;
    
    for (int i = 0; i <= N; i++){   
        if (arr[x][i] == 1 && check[i] == false){ //연결되어있고 다음노드는 탐색전이면 탐색
            dfs(i);
    	}
	}
}

int main(){
	int n;
	cin>>N>>E>>n;

	for(int i = 0; i < N; ++i)  //이차원배열 메모리할당
	{ 
		arr[i] = new int[N]; 
		memset(arr[i], 0, sizeof(int)*N);
	}

	for(int i = 0;i<E;i++)
	{
		cin>>U>>V;
		arr[U][V] = 1; //1:연결되어있음
		arr[V][U] = 1;
		check[U] = false;
		check[V] = false;
	}
	dfs(n);
}

 

너비우선탐색(Breadth-First Search)

현재 노드에서 탐색할 수 있는 모든 노드를 탐색한 뒤 넘어가는 방법

 

1. 시작노드에서 시작
2. 인접한 노드를 모두 방문한다.
3. 인접한 노드를 모두 방문했다면, 다른 노드로 이동
4. 다른 노드에서 인접한 노드들 또한 탐색
5. 이 과정을 모든 노드가 탐색될 때까지 반복한다.

너비우선탐색

소스코드(c++)

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

using namespace std;

int N, E; //노드개수, 에지개수
int U, V; //연결되어있는 노드 U,V
int **arr = new int*[N];  //연결여부
bool *check = new bool[N]; //탐색여부
queue<int> q;//큐

//너비우선탐색
void bfs(int n)
{ 
	q.push(n);//큐에 원소넣음
	check[n] = true; //탐색함

   while(q.size()!=0)
   { //큐가 비어있지 않은동안 반복
		int x = q.front();
		q.pop();//pop 
		cout<<x<<' ';  //큐의 가장 첫번째 원소 pop,출력
		
		for(int i = 0 ; i<=N; i++)
	    {
			if(arr[x][i]==1&&check[i]==false) //연결되어있고,방문하지 않은 노드 탐색
			{ 
			   check[i] = true;
			   q.push(i);
			   break;
			}
		} 
	}
}

int main(){

	int n;
	cin>>N>>E>>n;

	for(int i = 0; i <= N; ++i)  //이차원배열 메모리할당
	{ 
		arr[i] = new int[N]; 
		memset(arr[i], 0, sizeof(int)*N);
	}

	for(int i = 0;i<E;i++)
	{
		cin>>U>>V;
		arr[U][V] = 1; //1:U,V는 연결된노드
		arr[V][U] = 1;
		check[U] = false;
		check[V] = false;
	}

	bfs(n); //n번째노드부터 탐색
}

 

참고하면 좋은 문제

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

감사합니다^-^