📒DFS(Depth-First Search)

✍DFS(Depth-First Search)이란?

한국어로 깊이 우선 탐색으로 그래프를 완벽히 탐색한다.
시작지점부터 다음 Branch로 넘어가기 전 해당 Branch를 완벽히 탐색한다.

✍특징

📌특징

• 재귀함수 or 스택을 사용한다.
• 스택의 최상단 노드에 인접한 도드중 방문하지 않는 노드가 있다면 그 노드를 스택에 넣고 방문처리한다.
• 노드 방문시 방문 여부를 확인한다.
• 깊이가 너무 깊을 경우를 방지하기 위해 깊이 제한을 사용한다.

📌장, 단점

• 장점
  - 현 경로상의 노드만을 기억해 저장공간을 효율적으로 사용할 수 있다.
  • 목표 노드가 깊게 있을 경우 노드에 도달하는 시간이 적다.
• 단점
  -해가 없는 경로에 깊이 빠질 수 있다. -> 한계 깊이를 통해 방지 가능
  -얻어진 해가 반드시 최단경로는 아니다. -> 경로가 여러가지인 경우

✍사용방법

📌구현

Vector의 사용

[예시 그래프]

#include<iostream>
#include<vector>

using namespace std;

int check[10];
vector<vector<int> > graph(9);

void dfs(int x)
{
    check[x]=1;
    printf("%d ", x);
    
    for(int i=0; i<graph[x].size(); i++){
        	if(check[graph[x][i]]==0){
            	check[graph[x][i]]=1;
                dfs(graph[x][i]);
            }
    }
}

int main(){
	graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);
    
    graph[2].push_back(1);
    graph[2].push_back(7);
    
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    
    graph[4].push_back(3);
    graph[4].push_back(5);
    
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    graph[6].push_back(7);
    
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
    
    graph[8].push_back(1);
    graph[8].push_back(7);
	
    dfs(1);
}

출력 결과 값 : 1 2 7 6 8 3 4 5

📒BFS(Breadth-First Search)

✍BFS(Breadth-First Search)이란?

시작노드 방문 후 모든 인접한 노드 방문.
더이상 방문하지 않은 노드가 없을 때 까지 방문한다.

✍특징

📌특징

• 큐(Queue)를 이용하여 구현한다.
• 탐색시작 노드를 큐에 삽입하고 방문처리한다.
• 큐에서 노드를 꺼내고 인접한 노드를 모두 큐에 삽입한다.
• 최단경로를 구할 때 유리하다.

📌장, 단점

• 장점
  - 출발 노드에서 목표 노드까지의 최단 길이가 보장된다.
• 단점
  - 경로가 길 경우 탐색해야하는 노드 수가 증가한다. 많은 기억 공간을 필요로 한다.
  • 해가 존재하지 않는다면 모든 그래프 탐색 후에야 결과를 얻을 수 있다.
  • 해가 존재하지 않는 무한그래프의 경우 끝나지 않는다.

✍사용방법

📌구현

[예시 그래프]

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

using namespace std;

int check[10]
queue<int> q;
vector<vector<int> > graph(9)

void bfs(int x)
{
 	while(!q.empty()){
    	int x=q.front();
        q.pop();
        printf("%d ", x);
        
        for(int i=0; i<graph[x].size(); i++){
        	if(check[graph[x][i]==0]){
            	q.push(graph[x][i]);
                check[graph[x][i]=1;
			}
        }
	}   
}

int main(){
	graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);
    
    graph[2].push_back(1);
    graph[2].push_back(7);
    
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    
    graph[4].push_back(3);
    graph[4].push_back(5);
    
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    graph[6].push_back(7);
    
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
    
    graph[8].push_back(1);
    graph[8].push_back(7);
	
    q.push(1);
    check[1]=1;
    
    bfs(1);
}

출력 결과 값 : 1 2 3 8 7 4 5 6

✍DFS와 BFS의 차이점

• 노드를 저장할 때 BFS는 Queue DFS는 Stack을 사용한다.
• BFS는 정점기반, DFS는 에지 기반의 알고리즘이다.
• DFS가 메모리 공간의 활용에서 더 우수하다.
• BFS가 최적의 알고리즘이다.