공부 자료/알고리즘

[ 알고리즘 ] DFS 와 BFS

sshrik 2018. 8. 16. 11:32

[ 알고리즘 ] DFS 와 BFS



그래프 / 트리의 탐색 방법 중 깊이 우선 탐색과 너비 우선 탐색을 알아보도록 하겠습니다.

# DFS ( Depth First Search ), 깊이 우선 탐색

방법은 다음과 같습니다.

1 ) 자신을 방문했음 으로 표시한다.
2 ) 자신과 연결 된 노드 중 방문하지 않은 곳을 방문하고 1로 돌아감.
3 ) 방문 할 노드가 없다면 종료.

이 때 방문 한 순서를 알기 위해서는 하나의 인자를 추가해서 1번을 진행 한 바로 다음에 기록하면 됩니다.
또한 현재 방문하고있는 stack을 알기 위해서는 2번 앞뒤로 자기 자신 node를 stack에 push / pop 하면 됩니다.

void DFS(node *now, int *visit, int * ord, int indx)    {
    int i;

    if( visit[now->indx] == 1 ) return;
    
    // Check visit flag.
    visit[now->indx] = 1;
    
    // Check travel path.
    ord[indx++] = now->indx;

    // if want to check visited stack, push(now); here.
    for(i = 0; i < now->linkNum; i++)    {
        DFS( &(now->link[i]), visit, visited, ord, indx);
    }
    // if want tocheck visited stack, pop(now); here.
}


DFS로는 사이클 검사나 체스 경우의 수 조사 같은 것도 한다고 합니다. DFS가 만들기 더 쉬워서 이걸 쓴다고 합니다.
단순하게 생각하면, 한쪽으로 쭉 쭉 파고들어서 진행하니까, 깊이가 더 중요한 탐색에 쓰일 것 같다고 생각됩니다.

단순 검색 속도 자체는 BFS보다 느리다고 한다. 그래서 검색이 아닌 탐색에 쓰이는데, 백트래킹에 특히 자주 쓰인다고 합니다. ( 이는 공통 상위 노드를 가진 하위 노드들을 다 잘라 낼 수 있기 때문입니다. )

장점
  • 저장공간의 수요가 비교적 적다. ( 현 경로상의 노드만 기억하면 되니깐... )
  • 목표노드가 깊은 단계에 있을 때 빠른 해 구하기가 가능.
단점
  • 해가 없는 경로에 깊이 빠질 수 있는데, 이 때에는 깊이 제한을 주고 구하면 된다.
  • 얻은 해가 최단 경로임을 보장할 수 없다. ( 이 때에는 다익스트라를 쓰던지 해야할 수 있음. )





# BFS ( Breadth First Search ), 너비 우선 탐색

방법은 다음과 같습니다.

1 ) 자기 자신을 queue에 넣는다.
2 ) queue에서 하나를 꺼낸 노드를 자기 자신으로 지정한다.
3 ) 자기 자신을 방문 했음으로 표시한다.
4 ) 자신과 연결된 곳 중, 방문하지 않은 노드들을 queue에 순서대로 집어 넣는다.
5 ) 만약 queue가 비어있지 않다면 2번으로 돌아감.

역시 방문한 순서를 알고 싶다면, 5번을 진행하기 전에 자기 자신 노드의 순서를 기록하면 됩니다.


void BFS(node * map, int * ord)    {
    int visit[IND_MAX]= {0,};
    queue<node> toVisit = new queue<node>();


    int i, indx = 0;
    node now = map;

    queue.enqueue(now);

    do    {
        now = queue.dequeue();
        visit[now->indx] = 1;
        for(i = 0; i < now->linkNum; i++) {
            if(visit[now->link[i].indx] == 0)    {
                toVisit.enqueue(&(now->link[i]));
            }
        }
        
        // write path. ( travel path )
        ord[indx++] = now->indx;
    while(!queue.isEmpty());
}
BFS로는 최근접 경로나 페이스북 알 수 있는 친구 탐색 등에 쓰인다고 합니다. 무난하게 전수 조사 같은 곳에 쓰일 듯 싶습니다.
최단 거리를 알고 싶은 곳에 쓸 수 있으며, 또한 모든 노드 사이의 거리도 구할 수 있습니다.