[Algorithm] Graph-Theory - 3 : DFS와 BFS 한방에 이해하기.

1. DFS(깊이우선탐색) : 그래프나 트리를 탐색하는 알고리즘 중 하나. 시작 노드에서 깊이 우선 탐색을 수행하여 가능한 모든 경로를 탐색한다.

- 재귀적 방식이나 스택을 사용하여 구현할 수 있다.

- 경로 찾기, 연결요소 찾기, 사이클 검출 등의 사례로 사용된다.

DFS

 

2. 구현

dfs알고리즘 함수의 예시(재귀함수를 사용한 예시)

DFS알고리즘 함수의 예시(재귀)

- 인접리스트로 표현된 그래프, 시작노드, 목표노드를 매개변수로 받아 시작노드에서 목표노드까지의 경로를 찾아 배열로 반환한다.

- 경로를 찾지 못한 경우 null을 반환한다.

 

dfs 알고리즘 함수의 예시(stack)

DFS알고리즘 함수의 예시(재귀)

- 재귀 대신 while루프를 사용하여 stack에 있는 모든 노드를 처리한다.

- 스택의 강 항목은 현재 노드와 해당 노드까지의 경로를 포함한다.

 

 

3. 사용해보기 : 사이트 내 페이지간의 이동 경로 찾기

- 웹사이트의 페이지들이 그래프로 표현되어 있고, 각 노드가 페이지를 나타내며, 엣지가 페이지 간의 링크를 나타낸다고 가정할 경우

- 사용자가 특정 페이지에서 다른 페이지로 이동하는 경로를 찾고 싶다면, DFS 알고리즘을 사용하여 시작페이지에서 목표 페이지까지의 경로를 찾을 수 있다.

 

Express에서 dfs함수를 구현한 예시

express 서버에서의 사용 예시

 

 

4. BFS(너비우선탐색) : 그래프나 트리의 각 레벨을 너비 방향으로 탐색하는 알고리즘.

- 시작 노드부터 모든 인접한 노드를 방문한 다음, 각 인접 노드의 인접한 노드를 방문하는 방식으로 탐색한다.

- 큐(Queue)자료구조를 사용하여 방문할 노드를 저장하고 처리한다.

BFS

 

5. 구현

queue를 활용한 BFS의 구현

 

DFS와 BFS의 차이점 정리

DFS와 BFS의 차이점 정리