DFS & BFS

[duyeonnn]

DFS

Depth First Search의 줄임말로 정점의 자식들을 먼저 탐색하는 방식이다.

스택 또는 재귀함수로 구현한다.

BFS

Breath Frist Search의 줄임말로 정점에서 시작해 인접한 노드를 먼저 탐색하는 방법.

주로 두 노드 사이의 최단경로를 찾고 싶을때 사용

큐를 이용해 구현한다

BFS DFS 둘다 N은 노드, E는 간선일때, 인접리스트의 경우 O(N+E)의 시간복잡도를, 인접 행렬의 경우 O(N^2)의 시간 복잡도를 가진다

[tmfrlrkvlek]

그래프의 탐색 기법으로 BFS(Breadth First Search)는 너비 우선 탐색, DFS(Depth First Search)는 깊이 우선 탐색입니다. 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다. BFS는 간선의 모든 가중치가 같을 때 최단 거리를 구하는 알고리즘으로, 시작 정점을 기준으로 가까운 정점을 먼저 방문합니다. 큐를 이용하여 선입선출의 원칙으로 탐색합니다. DFS는 루트 노드에서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법으로 자기 자신을 호출하는 순환 알고리즘의 형태입니다.

[inuinseoul]

그래프를 탐색하는 방법에는 대표적으로 BFS와 DFS가 있습니다.

• BFS는 넓이우선탐색으로, 시작점에서부터 가까운 노드부터 탐색해나가는 것입니다. 즉, 너비를 우선적으로 탐색합니다. 일반적으로 큐를 통해 구현할 수 있습니다. 최단거리 문제를 해결할 경우 유용합니다.
• DFS는 깊이우선탐색으로, 시작점에서 최대한 멀리까지 노드를 탐색하고 반복해나가는 것입니다. 즉, 깊이를 우선적으로 탐색합니다. 일반적으로 스택 혹은 재귀를 통해 구현할 수 있습니다. 각 경로의 특징을 저장할 필요가 있을 경우 유용합니다.

[sustainable-git]

• DFS와 BFS는 Graph를 탐색하는 방법입니다. DFS(깊이 우선 탐색)는 다음 분기를 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이고, BFS(너비 우선 탐색)는 인접 노드를 먼저 탐색하는 방법입니다.
• DFS는 Stack 또는 재귀함수를 이용해 구현하고, BFS는 Queue를 이용해 구현합니다.
• 최단 거리를 구해야하는 경우나 거리가 가까운 경우에는 BFS가 유리하고, Graph가 크거나 경로 자체가 중요한 경우에는 DFS가 유리합니다.