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. 그래프 순회 3. 최단 경로 4. 최소비용 신장트리
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (트리,그래프)
          1.   그래프
                1. 그래프
                2. 그래프 종류
                3. 그래프 표현
            1.   그래프 용어
            2.   그래프 알고리즘
              1.   1. 그래프 알고리즘
                  2. 그래프 순회
                  3. 최단 경로
                  4. 최소비용 신장트리
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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