BFS&DFS.md

BFS/DFS

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

• 루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식
• 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함

알고리즘

BFS()
    큐 생성
    루트 v를 큐에 삽입
    while(큐가 비어있지 않을 때){
        temp <- 큐의 첫  번째 원소 반환
        temp 방문
        for (temp와 연결된 모든 간선에 대해){
            next <- t의 자식노드
            next를 큐에 삽입
        }
    }
end BFS()

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

• 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 방법
• 가장 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용해서 구현

알고리즘

DFS(v)
    v 방문

    for(v의 모든 자식노드 w){
        if 방문하지 않은 곳일때
            DFS(w)
    }
end DFS()