[C언어] BFS와 DFS

그래프의 정점을 모두 한번씩 방문하는 알고리즘을 순회 알고리즘(Traversal Algorithm)이라고 한다.

크게 두가지 종류가 있는데,

하나는 깊이 우선 탐색(DFS,Depth First Algorithm)이고, 하나는 너비 우선 탐색(BFS,Breadth First Algorithm)이다.

1. 깊이 우선 탐색 (DFS)

인접한 정점이 존재한다면 계속 한 우물만 깊게 파고드는 타입. 

만약 인접한 정점이 존재하지 않는 정점(이른바 막다른 길)을 발견한다면, 이 전에 있었던 정점으로 돌아가서 또 새롭게 팔 우물(..)이 있는지 살펴본다.

일단 "길이 있으면 가고 본다!!" 라는 막무가내 타입이기 때문에,

①인접해있고 ②한번도 방문한 적이 없다면 , 바로 해당 정점으로 탐색하러 가면 된다.

재귀 함수만 안다면 쉽게 구현할 수 있다

(준비물 : 정점의 방문 여부를 체크해줄 배열, 인접 여부를 체크해줄 행렬(혹은 리스트), 재귀함수에 대한 개념)

2. 너비 우선 탐색 (BFS)

깊이 우선 탐색이 날카롭고 "깊게" 파고드는 탐색 알고리즘이었다면 

너비 우선 탐색은 "넓게 넓게" 파고드는 탐색 알고리즘이라고 보면 된다.

일단 인접한 정점을 발견하면 거길 탐색하고 다시 캠프로 돌아와서 다음 인접 정점을 탐색하는 식이다.

이런 식으로 하다보니 자연스럽게 레벨 별로 탐색이 이루어진다.

(레벨 0인 정점) (레벨 1의 정점들) (레벨 2의 정점들)....(레벨 n의 정점들) 바로 이렇게 말이다.

DFS와 마찬가지로 방문여부를 알려주는 배열, 인접 여부를 알려주는 행렬(혹은 리스트)가 있으면 되는데, 추가로 "큐"가 필요하다.

일단 인접한 정점을 발견하면 큐에 넣어두고,

큐가 다 비어버릴 때까지 Pop 시키면서 해당 Pop 정점에 대해 또 인접한 정점을 찾아보고, 찾으면 또 큐에 넣고, 주변을 다 살폈으면 다시 큐에서 Pop시켜서 또 인접한 정점을 찾아보는 과정의 반복이다.

======================================================================================

백준 알고리즘 1260번을 풀면 DFS와 BFS를 간단히 구현하는 법을 배울 수 있다.

다음은 내가 풀었던 DFS와 BFS 코드다.

#include <stdio.h>
 
int Graph[1001][1001]={0};
int DFSvisit[1001]={0};
int BFSvisit[1001]={0};
int queue[1001];
 
 
void DFS(int v,int N){
    int i;
 
    DFSvisit[v]=1;
    printf("%d ",v);
    for(i=1;i<=N;i++){
        if(Graph[v][i]==1 && DFSvisit[i]==0){
            DFS(i,N);
        }
    }
 
    return;
}
 
void BFS(int v,int N){
    int front=0,rear=0,Pop,i;
    
    printf("%d ",v);
    queue[0]=v;
    rear++;
    BFSvisit[v]=1;
 
    while(front<rear){
        Pop=queue[front];
        front++;
        
        for(i=1;i<=N;i++){
            if(Graph[Pop][i]==1 && BFSvisit[i]==0){
                printf("%d ",i);
                queue[rear]=i;
                rear++;
                BFSvisit[i]=1;
            }
        }
    }
 
    return;
}
        
 
 
int main(){
    int N,M,Start;
    int i,x,y;
 
    scanf("%d%d%d",&N,&M,&Start);
    
    for(i=0;i<M;i++){
        scanf("%d%d",&x,&y);
        Graph[x][y]=1;
        Graph[y][x]=1;
    }
 
    DFS(Start,N);
    printf("\n");
    BFS(Start,N);
 
    return 0;
}