Graph Traversal   그래프 순회

(2020-03-10)

DFS, Depth First Search, 깊이 우선 탐색, BFS, Breadth First Serach, 너비 우선 탐색

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)인 자료구조를 활용


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 최단 경로 4. 최소비용 신장트리

 
        최근수정     요약목록     참고문헌