[알고리즘] 그래프 탐색

그래프 탐색이란?

▶  어떤 것들이 연속해서 이어질 때 모두 확인하는 방법

▶  Graph: Vertex (어떤 것) + Edge (이어지는 것)

 

그래프 탐색 종류

출처: https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

▶  BFS: Breadth-fist search (너비 우선 탐색)

      ▷ 자기 자식을 우선으로 탐색함

      ▷ 자기 자식 다 끝나고 나면 자식의 자식 탐색

 

▶ 아이디어:

1. 시작점에 연결된 vertex 찾기

2. 찾은 vertex를 queue에 저장

3. queue의 가장 먼저인 것을 뽑아서 반복

 

 

▶  DFS: Depth-first search

      ▷ 자식 탐색

      ▷ 그 후, 자식의 자식 탐색

      ▷ 자식이 없다면 위로 올라와서 그 다음 자식 탐색

 

▶ 아이디어:

1. 시작점에 연결된 vertex 찾기

2. 연결된 vertex를 계속해서 찾음 (끝날 때 까지)

3. 더이상 연결된 vertex 가 없을 경우 올라가기

 

 

 BFS와 DFS 개념, 구현 방법, 코드는 다른 게시물에서 자세히 정리해뒀다.