BFS와 DFS – 차이점

BFS란 무엇입니까?

BFS는 데이터를 그래프화하거나 트리를 검색하거나 구조를 횡단하는 데 사용되는 알고리즘입니다. 이 알고리즘은 정확한 너비 방식으로 그래프의 모든 키 노드를 효율적으로 방문하고 표시합니다.

이 알고리즘은 그래프에서 단일 노드(초기 또는 소스 포인트)를 선택한 다음 선택한 노드에 인접한 모든 노드를 방문합니다. 알고리즘이 시작 노드를 방문하고 표시하면 가장 가까운 방문하지 않은 노드로 이동하여 분석합니다.

일단 방문하면 모든 노드가 표시됩니다. 이러한 반복은 그래프의 모든 노드를 성공적으로 방문하고 표시할 때까지 계속됩니다. BFS의 전체 형태는 너비 우선 검색입니다.

DFS란 무엇입니까?

DFS는 깊이 방향으로 그래프나 트리를 찾거나 탐색하는 알고리즘입니다. 알고리즘의 실행은 루트 노드에서 시작하여 역추적하기 전에 각 분기를 탐색합니다. 반복에서 막다른 골목이 나타날 때마다 기억하고, 후속 정점을 얻고, 검색을 시작하기 위해 스택 데이터 구조를 사용합니다. DFS의 전체 형태는 깊이 우선 탐색입니다.

BFS와 DFS 이진 트리의 차이점

BFS와 DFS의 중요한 차이점은 다음과 같습니다.

BFS	DFS
BFS 목적지까지의 최단 경로를 찾아냅니다.	DFS는 하위 트리의 맨 아래로 이동한 다음 역추적합니다.
BFS의 전체 형태는 너비 우선 검색입니다.	DFS의 전체 형태는 깊이 우선 탐색입니다.
대기열을 사용하여 다음 방문 위치를 추적합니다.	스택을 사용하여 다음 방문 위치를 추적합니다.
BFS는 트리 수준에 따라 순회합니다.	DFS는 트리 깊이에 따라 탐색합니다.
FIFO 목록을 사용하여 구현됩니다.	LIFO 목록을 사용하여 구현됩니다.
DFS에 비해 더 많은 메모리가 필요합니다.	BFS에 비해 메모리가 덜 필요합니다.
이 알고리즘은 가장 얕은 경로 솔루션을 제공합니다.	이 알고리즘은 가장 얕은 경로 솔루션을 보장하지 않습니다.
BFS에서는 역추적(backtracking)이 필요하지 않습니다.	DFS에는 역추적(backtracking)이 필요합니다.
결코 유한 루프에 갇힐 수 없습니다.	무한루프에 갇힐 수 있습니다.
목표를 찾지 못한 경우 솔루션을 찾기 전에 많은 노드를 확장해야 할 수도 있습니다.	목표를 찾지 못하면 리프 노드 역추적이 발생할 수 있습니다.

BFS의 예

다음 BFS 예제에서는 정점이 6개인 그래프를 사용했습니다.

BFS의 예

단계 1)

0~6까지 XNUMX개의 숫자로 구성된 그래프가 있습니다.

단계 2)

0 또는 XNUMX이 루트 노드로 표시되었습니다.

단계 3)

0이 방문되어 표시되고 대기열 데이터 구조에 삽입됩니다.

단계 4)

나머지 0개의 인접 노드와 방문하지 않은 노드를 방문하고 표시한 후 대기열에 삽입합니다.

단계 5)

모든 노드를 방문할 때까지 순회 반복이 반복됩니다.

DFS의 예

다음 DFS 예에서는 5개의 정점을 갖는 무향 그래프를 사용했습니다.

단계 1)

우리는 정점 0에서 시작했습니다. 알고리즘은 정점을 방문 목록에 넣고 동시에 모든 인접 정점을 방문 목록에 넣는 것으로 시작합니다. 데이터 구조 스택이라고 부른다.

단계 2)

스택의 맨 위에 있는 요소(예: 1)를 방문하고 인접한 노드로 이동합니다. 이미 0을 방문했기 때문입니다. 따라서 정점 2를 방문합니다.

단계 3)

정점 2에는 4의 근처에 방문하지 않은 정점이 있습니다. 따라서 이를 스택에 추가하고 방문합니다.

단계 4)

마지막으로 마지막 정점 3을 방문할 것인데, 방문하지 않은 인접 노드가 없습니다. DFS 알고리즘을 사용하여 그래프 순회를 완료했습니다.

BFS의 응용

BFS의 응용 프로그램은 다음과 같습니다.

비가중 그래프

BFS 알고리즘은 최단 경로와 최소 스패닝 트리를 쉽게 생성하여 가능한 최단 시간에 높은 정확도로 그래프의 모든 정점을 방문할 수 있습니다.

P2P 네트워크

BFS는 피어 투 피어 네트워크에서 가장 가까운 또는 이웃 노드를 모두 찾는 데 구현할 수 있습니다. 이렇게 하면 필요한 데이터를 더 빨리 찾을 수 있습니다.

웹 크롤러

검색 엔진 또는 웹 크롤러는 BFS를 사용하여 여러 수준의 인덱스를 쉽게 구축할 수 있습니다. BFS 구현은 웹 페이지인 소스에서 시작하여 해당 소스의 모든 링크를 방문합니다.

네트워크 방송

브로드캐스트된 패킷은 BFS 알고리즘에 의해 안내되어 주소가 있는 모든 노드를 찾아 도달합니다.

DFS의 응용

DFS의 중요한 응용 프로그램은 다음과 같습니다.

가중 그래프

가중치 그래프에서 DFS 그래프 순회는 최단 경로 트리와 최소 스패닝 트리를 생성합니다.

그래프에서 사이클 감지

DFS 중에 백 에지를 발견하면 그래프에 주기가 있습니다. 따라서 그래프에 대해 DFS를 실행하고 뒤쪽 가장자리를 확인해야 합니다.

길 찾기

두 정점 사이의 경로를 검색하기 위해 DFS 알고리즘을 전문화할 수 있습니다.

토폴로지 정렬

주로 작업 그룹 간의 주어진 종속성에서 작업을 스케줄링하는 데 사용됩니다. 컴퓨터 과학에서는 명령어 스케줄링, 데이터 직렬화, 논리 합성, 컴파일 작업 순서 결정에 사용됩니다.

그래프의 강력하게 연결된 구성 요소 검색

DFS 그래프에서 그래프의 모든 정점에서 나머지 정점으로의 경로가 있을 때 사용됩니다.

단 하나의 솔루션으로 퍼즐 풀기

DFS 알고리즘은 방문 세트의 기존 경로에 노드를 포함하여 미로에 대한 모든 솔루션을 검색하도록 쉽게 적용할 수 있습니다.