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

(2023-11-03)

1. 그래프 순회 방법 (Graph Traversal)그래프 상에서, 
     - 모든 정점을 한번씩 만 방문하거나, 
     - 모든 정점을 한번씩 만 방문하면서 목표 정점을 찾아가거나,
     - 또한, 특정 정점에서 다른 정점으로 갈수 있는지, 서로 연결되었는지 등을
     - 확인하는 방법                                 ☞ 그래프 알고리즘 참조

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

  ㅇ (용도) 
     - 특정 정점에서 다른 정점으로 갈수 있는지, (연결성 검사, 경로 존재 검사)
     - 서로 연결되었는지, (인접성 검사)
     - 내부에 순환을 포함하는지 등을 확인하거나, (루프 검사)
     - 미로 퍼즐 (미로 찾기, 출구 찾기) 등 
     * 다양한 그래프 알고리즘의 기초가 됨

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

  ㅇ (참고)
     - 다른 알고리즘과 마찬가지로, 알고리즘 그 자체 뿐 만아니라, 
     - 그래프 표현 방식(즉,자료구조)에 따라서 구현 용이성,성능 등이 영향 받음


2. 그래프 탐색의 대표적인 방식 둘(2)깊이 우선 탐색 방법 (Depth First Search, DFS)
     - 방법 요약 : 특정 정점에서 먼저 자식을 방문 후 더이상 자식이 없으면 전 단계 형제를 방문
     - 유용한 자료구조 : 스택 이용
     - 다음 미방문 노드 선택 기준
        . 더 깊게
        . 현재 노드너비 우선 탐색 방법 (Breadth First Serach, BFS)
     - 방법 요약 : 특정 정점에서 모든 형제를 방문 후에야 자식을 방문
     - 유용한 자료구조 :  이용
     - 다음 미방문 노드 선택 기준
        . 더 넓게
        . 이전 노드

그래프 알고리즘
   1. 그래프 알고리즘   2. 그래프 순회 (DFS,BFS)   3. 깊이 우선 탐색 (DFS)   4. 너비 우선 탐색 (BFS)   5. 위상 정렬   6. 최소 신장 트리   7. 최단 경로   8. 다익스트라 알고리즘   9. 플로이드 알고리즘  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"