[DFS와 BFS의 차이]

DFS(깊이 우선 탐색)

인접하는 한 정점에서 갈곳이 없을 때 까지 탐색하고 되돌아와 다음 정점을 탐색하는 방법

 

대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 

 

 

//인접 행렬로 구현

void dfs(int x)
{
    check[x] = true;
    
    for(int i = 1; i <= V ; i++)
    {
    	if(graph[x][i] == 1 && !check[i])
        	dfs(i);
    }
}

 

시간복잡도는 O(V^2)이다. V는 간선의 갯수 

 

//인접 리스트로 구현

void dfs(vector<int> graph, bool check, int x) 
{

    check[x] = true;
    
    for(int i = 0; i < graph[x].size(); i++)
    {
    	int next = graph[x][i];
        if(!check[next])
        	dfs(next);
    }
}

 

 

시간 복잡도는 O(V+E)이다. V는 간선 E는 노드의 갯수

 

 

 

//스택으로 구현

void dfs(vector <int> adj,int start) {
    int cur = start;
    s.push(cur); 
    visited[cur]=true;
    s.pop();
   
    while(s.size()){
        cur = s.top();
        for(int i = 0; i < v.size(); i++){
            if(!visited[adj[cur][i]){
                s.push(cur); //cur이 끝나지 않았으니 다시 넣음
                s.push(adj[cur][i]); //다음 값 넣음
                visited[cur]=true;
                break;
            }
        }
    }
}

 

DFS의 장점
1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음(BFS에 비해)
2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
3. 구현이 너비 우선 탐색보다 간단함
 
DFS의 단점
1.BFS에 비해 느리다.
2.해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
2.얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

 

 

 

BFS(너비 우선 탐색)

한 정점을 기준으로 인접하는 모든 정접을 탐색하는 기법

 

 

void bfs(){
  queue<int> q; //Queue 생성
  q.push(0); //초기 시작점 저장
  check_bfs[0] = true; //초기 방문 체크
  
  while(!q.empty()){
    int current = q.front();
    q.pop();

    for(int i=0;i<v[current].size();i++){
      int next = v[current][i];
      
      if(!check_bfs[next]){
        check_bfs[next] = true;
        q.push(next);
      }
    }
  }
}

 

 

 

 

 

 

 

BFS의 장점
1. 노드의 수가 적고 깊이가 얕은 경우 빠르다.
2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.
3.최단경로임을 보장한다.


BFS의 단점
1. 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아진다.