그래프 탐색이란?

그래프 탐색이란? (그래프 순회 방법)

그래프 알고리즘은 여러가지 방법이 존재한다.

1. 그래프 내 모든 정점을 순회하는 방법

2. 작업 사이에 특정 의존(순서)관계가 있을 때 이를 정렬 시키는 방법

3. 루프가 없는 그래프(신장 트리)를 생성 시키는 방법

4. 최소 신장 트리를 작성하는 방법

5. 그래프 상에서 최단 경로를 탐색하는 방법

 

아래에 그림은 그래프 알고리즘 관련 사진이다.

다음과 같은 지형이 있을 때, 임의의 한 곳 (A,B,C,D) 에서 출발하여 a~f 까지 "모든 다리를 한 번씩 건널 수 있는 가?" 라는 문제이다.

이러한 문제를 컴퓨터에 표현하는 알고리즘이다.

출처. http://dblab.duksung.ac.kr/ds/pdf/Chap10.pdf

여기서 그래프 탐색은, 1번 그래프 내 모든 정점을 순회하는 방법이다.

하나의 시작점 Node에서 연결된 Node들을 모두 찾는 것을 의미한다.

그래프 탐색할 때, 시작점 Node는 우리가 정하기 나름이다.

그리고 시작점으로 부터 다른 Node들을 찾아가는 것이 그래프 탐색이다.

 

 

 

그래프 탐색에 대표적인 알고리즘은?

- 깊이 우선 탐색 (Depth First Search, DFS)

- 너비 우선 탐색 (Breadth First Search, BFS)