DFS   Depth First Search   깊이 우선 탐색

1. 깊이 우선 탐색 방법 (Depth First Search, DFS)

  ㅇ 방법 요약
     - 갈 수 있는데까지 가보다가, 더이상 진행 못하면 거슬러 올라와서(되돌아와서),
        . 즉, 최대한 멀리 (깊숙히) 있는 노드를 우선으로 탐색하는 방식을 취함
     - 되돌아온 갈림길에서, 미방문 노드가 있으면, 또다시 갈 수 있는데까지 가서 탐색하는 방법

  ㅇ 구현 방법 : 주로, `스택 반복` 또는 `재귀 반복`으로 구현

  ㅇ 시간 복잡도 : 선형 시간
     - O(N + M) : 각 정점을 1번씩 만 방문하고, 각 간선을 1번씩 만 지나감
        . 여기서, N은 정점의 수, M은 간선의 수


2. 알고리즘 구현 例) (스택 반복 구현)

  ㅇ 구현 개요
     - 매 정점 마다, 인접 정점들 중 미방문 정점들을 스택에 추가하고,
     - 방문할 정점을 탐색할 때, 스택에서 하나씩 꺼냄

  ㅇ 구현 특징
     - 자료구조  : 후입선출(LIFO)인 `스택` 자료구조를 활용
     - 입력 : 특정 그래프(G), 시작 정점(v)
        . 여기서, G는 인접 리스트에 의한 그래프 표현으로 가정 함
     - 출력 : 방문한 정점들이 열거된, 크기가 |V|인, 배열 또는 리스트 (visited)
        . visited[i]가, true이면 이미 방문, false 이면, 미 방문

     
stackDFS(G, v)
    stack = createStack()              ①
    visited = createArray(|V|)         ②
    for (i=0; i<|V|; i++)              ③
        visited[i] = FALSE

    push(stack, v)                     ④
    while (not isEmpty(stack))         ⑤
        c = pop(stack)                 ⑥
        visited[c] = TURE              ⑦
        for i in adjacencyList(G, c)   ⑧
            if not visited[i]          ⑨
                push(stack, i)

    return visited;                    ⑩ 

  ㅇ 구현 단계
     - ① 스택 자료구조의 생성 (미방문 정점들로써, 빈 스택)
     - ② 방문 여부를 기록하게될 정점들의 배열(또는,리스트)의 생성 (빈 배열)
     - ③ 방문 정점 배열에 대한 초기화 (전체 미방문으로 false 설정)
     - ④ 시작 정점을 빈 스택에 추가
     - ⑤ 미방문 정점들을 들어있는 스택이 빌 때까지 반복
     - ⑥ 방문할 정점을 스택에서 꺼냄
     - ⑦ 현재 방문 정점에 방문했음(true)을 기록
     - ⑧ 인접리스트에 의한 그래프 표현(G)으로부터, 인접 정점들을 추출하고, 차례대로 탐색
     - ⑨ 이들 중에 해당 정점이,
        . 미방문이면, 방문할 정점이므로, 미방문 스택에 이를 추가하고, ⑤ 반복
        . 방문이면, 그냥 ⑤ 반복
     - ⑩ 방문 여부 기록된 배열(visited)을 반환


3. 알고리즘 구현 例) (재귀 반복 구현)

  ㅇ 구현 특징
     - 입력 : 특정 그래프(G), 시작 정점(v)
        . 여기서, G는 인접 리스트에 의한 그래프 표현으로 가정 함
     - 외부 데이터 : 알고리즘이 접근하여, 읽고 수정 가능한 배열 (visited)
        . 알고리즘 동작 이전에, 정점 수 |V| 크기로, 초기화된 visited 배열을, 생성할 필요 있음
        . visited[i]가, true이면 이미 방문, false 이면, 미 방문

      
recursiveDFS(G, v)
    visited[v] = TRUE               ①
    for i in adjacencyList(G, v)    ②
        if not visited[i]           ③
            recursiveDFS(G, i)      ④

  ㅇ 구현 단계
     - ① 입력(v)으로 주어진, 현재 방문 정점에 방문했음(true)을 기록
     - ② 인접리스트에 의한 그래프 표현(G)으로부터, 
        . 현재 방문 정점의 인접 정점들을 추출하고, 이들을 차례대로 탐색
     - ③ 만일 해당 정점이 미방문이면,
     - ④ 재귀 반복(recursiveDFS)