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

(2021-02-21)

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)인 `` 자료구조를 활용 . 자연스럽게 최단 경로를 일러줌 . 중간에 거치는 정점들을 저장해 둘 필요 있음 ㅇ 알고리즘의 표현 - 입력 : 특정 그래프(G), 시작 정점(n) - 출력 : 도달 가능 모든 정점들에 대한 배열(방문 여부 true/false 또는 각각의 경로 길이) ㅇ ... (작성중) ...


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 위상 정렬 4. 최소비용 신장트리 5. 최단 경로 6. 다익스트라 알고리즘 7. 플로이드 알고리즘
  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. 그래프 표현
                4. 평면 그래프
            1.   그래프 용어
            2.   그래프 알고리즘
              1.   1. 그래프 알고리즘
                  2. 그래프 순회 (DFS,BFS)
                  3. 위상 정렬
                  4. 최소비용 신장트리
                  5. 최단 경로
                  6. 다익스트라 알고리즘
                  7. 플로이드 알고리즘
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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