Graph Traversal, Graph Search   그래프 순회, 그래프 탐색

1. 그래프 순회 방법 (Graph Traversal)

  ㅇ 그래프 상에서, 
     - 모든 정점을 한번씩 만 방문하거나, 
     - 한번씩 만 방문하여 목표 정점을 찾아가는 방법

  ㅇ (명칭) 
     - 때론, 그래프 탐색/그래프 검색(Graph Search) 방법 이라고 함

  ㅇ (요건)
     - 방문했던 곳을 유지해야 함
     - 아직 방문하지 않은 곳들에 대한 체계적인 다음 방문 방법이 제시되어야 함
     - 어떤 식으로든 정점들이 순서화되어 있어야 함

  ㅇ (용도) 
     - 특정 정점에서 다른 정점으로 갈수 있는지,
     - 서로 연결되었는지,
     - 내부에 순환을 포함하는지 등을 확인하거나,
     - 미로 퍼즐 등에 사용 

  ㅇ (대표적인 例 둘)
     - 깊이 우선 탐색 방법 (Depth First Search, DFS)
     - 너비 우선 탐색 방법 (Breadth First Serach, BFS)


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

  ㅇ 갈 수 있는데까지 가보다가, 더이상 진행 못하면 거슬러 올라가며(되돌아와서),
     - 아직 가보지 못한 노드가 있으면, 또다시 갈 수 있는데까지 가보는 방법
     - 목표 정점을 탐색할 때, 하나의 길을 끝까지 따라가며 탐색하는 방법

  ㅇ 특징
     - 사용 자료구조  :  후입선출(LIFO)인 `스택` 자료구조를 활용
     - 시간 복잡도  : 선형 시간

  ㅇ 알고리즘의 표현
       
DFS(v) {
    for (i=0; i<n; i++)
        visited[i] = false;
    stack = createStack();
    visited[v] = true;

    while (not isEmpty(stack))
        if (visited[adjacent w] = false)
            push(stack, v);
            visited[w] = true;
            v = w;
        else
            v = pop(stack);
}

  ㅇ ... (작성중) ...


3. 너비 우선 탐색 방법 (Breadth First Serach, BFS)

  ㅇ 우선 가까운 인접 노드를 모두 방문한 후에, 그 다음 가까운 인접 노드를 방문하며 진행하는 방법
     - 목표 정점을 탐색할 때, 시작점에 가까운 근처 정점부터 탐색하는 방법 

  ㅇ 특징
     - 사용 자료구조  :  선입선출(FIFO)인 `큐` 자료구조를 활용
        . 자연스럽게 최단 경로를 일러줌
        . 중간에 거치는 정점들을 저장해 둘 필요 있음

  ㅇ 알고리즘의 표현
     - 입력 : 특정 그래프(G), 시작 정점(n)
     - 출력 : 도달 가능 모든 정점들에 대한 배열(방문 여부 true/false 또는 각각의 경로 길이)
     
  ㅇ ... (작성중) ...