[알고리즘] 트리탐색 : DFS, BFS

BFS(Breadth First Search)

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

BFS 의사코드

BFS (G, V)
    let Q be a queue // 큐 생성
    label V as discovered 
    Q.enqueue(V) // 루트 v를 큐에 삽입

    while Q is not empty do // 큐가 비어 있지 않은 경우
        v := Q.dequeue() // 큐의 원소 반환

        if v is the goal then 
            return v

        // v와 연결된 모든 간선에 대해서
        for all edges from v to w in G.adjacentEdges(v) do
        	// w가 v의 자식노드이면 큐에 삽입
            if w is not labeled as discovered then
                label w as discovered
                w.parent := v
                Q.enqueue(w)

DFS

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

DFS(G, v)
    let S be a stack // 스택 생성
    S.push(v) // 스택에 v 삽이
    while S is not empty do // 스택이 비어있지 않을 동안
        v = S.pop() // 현재 탐색 하고 있는 정점을 v에 넣는다.

        // 만약 v가 탐색되지 않았으면, 탐색 완료 표시를 한다.
        if v is not labeled as discovered then
            label v as discovered
            현재 정점 v의 모든 인접한 정점 w를 스택에 넣는다.
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)