[자료구조] 그래프 탐색

[자료구조] 그래프 탐색

그래프 탐색

그래프의 모든 정점을 방문하는 것을 그래프 탐색이라고 한다.
그래프 구조의 자료를 검색하고, 저장하고, 연산하는데 필요한 기본 알고리즘을 제공한다.
그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색이 있다.

---

너비 우선 탐색(BFS : Breath First Search)

서울에서 부산까지 가는 길에 모든 도시를 하나도 빠짐없이 차례로 방문하는 방법이다.

• 큐

---

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

서울에서 부산까지 가는 길에 방문할 수 있는 도시는 우선 방문하되 같은 지역에 있는 도시가 있다면 그 중 하나만 방문하고 간다.

되돌아오는 길에 나머지 도시들을 차례로 방문하는 방법이다.

• 스택

---

출처

• https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html