DFS / BFS

# DFS (Depth First Search)

 

'깊이 우선 탐색'이라는 이름에서 알 수 있듯이, 최대한 깊숙이 들어가서 확인하고, 돌아가서 또 반복하며 트리나 그래프를 탐색한다.

가장 마지막에 만났던 갈림길의 정점으로 돌아가서 다시 DFS를 진행해야 하므로 후입 선출 구조의 스택을 사용한다.

input 사이즈가 너무 크지 않다면 스택뿐만 아니라 재귀 호출로도 구현 가능하다.

 

- 재귀를 이용한 코드

void recur_dfs(int node)
{
    visited[node] = true;
    for(int next=0; next<N; next++)
    {
        if(!visited[next] && Graph[node][next]) recur_dfs(next);
    }
}

- 스택을 이용한 코드

void stack_dfs(int node)
{
    bool visited[MAX_N] = {false};
    top = -1;
    Stack[++top] = node; //처음시작노드 추가
    while(top!=-1)
    {
        int curr = Stack[top--];
        if(!visited[curr])
        {
            visited[curr] = true;
            cout<<curr<<' ';
            for(int next=0; next<N; next++)
            {
                if(!visited[next]&&Graph[curr][next])
                {//인접 노드중 정점간 간선있고 방문한 적 없으면
                    Stack[top++] = next;
                }
            }
        }
    }
}

 

# BFS (Breadth First Search)

 

'너비 우선 탐색' 이므로 갈림길에 연결된 모든 길을 탐색한 후, 다시 연결된 모든 길을 탐색한다.

인접 정점들을 탐색한 후, 다시 BFS를 진행해야 하므로 선입 선출 구조의 큐를 사용한다.

가중치가 없는 그래프에서는 BFS로 최단 경로를 구할 수 있다.

 

- 큐를 이용한 코드 (주석을 해제하면 최단 경로를 구할 수 있다.)

void bfs(int node)
{
    bool visited[100] = {false};
    //dist[node] = 0;
    front = rear = -1;
    visited[node] = true;
    queue[++rear] = node;
    while(front!= rear)
    {
        int cur=queue[++front];

        for(int next=0; next<N; ++next)
        {
            if(!visited[next]&&graph[cur][next])
            {
                visited[next] = true;
                //dist[next] = dist[cur]+1;
                queue[++rear] = next;
            }
        }
    }
}