[TIL][Sat] BFS / DFS in Graph

DFS vs BFS, 언제 무엇을 써야 할까?

어느 탐색 전략이 좋은지는 그래프의 모양에 따라 효율이 갈리니 모양과 용도를 보고 선택하자!

DFS>BFS

DFS가 BFS보다 우월한 성능을 낼 때

1. 높은 분기 계수(branching factor)를 가진 두껍게 연결된 그래프에서(thickly connected graphs DFS가 BFS보다 더 좋은 성능을 낸다.[같은 뜻의 비슷한 표현] 그래프의 간선이 많고(=밀도가 높다/dense하다) 평균 인접 노드 수가 노드 수에 비해 높다면 너비 우선 검색은 긴 대기열을 가진다. 그에 비해 DFS는 적은 스택을 가지므로 DFS가 좀 더 성능이 좋을 것이다.)
2. 해답(solution)이 가장 먼 자식 노드에 있을 것 같으면 DFS가 더 좋은 선택이 된다.

BFS>DFS

BFS가 DFS보다 우월한 성능을 낼 때

1. 낮은 분기 계수를 가진(간선edge가 얼마 없는) 희소 그래프(sparse graph)에서 더 우월한 성능을 보인다. 희소 그래프에서 DFS는 긴, 연관성이 떨어지는 체인에 막힐 수 있다.
2. 해답(solution)이 현재 노드current node의 이웃에 있을 때 BFS를 선택하는 것이 좋다.

분기 계수가 왜 BFS와 DFS 성능 차이를 불러올까?

먼저 BFS의 관점으로 보자면, 분기 계수가 증가함에 따라 노드(의 개수)가 기하급수적으로 증가하기 때문이다. BFS는 같은 레벨의 노드들을 전부 훑고 지나가기 때문에 한 레벨에 많은 노드들이 존재하는, 즉 부모(상위 노드)가 많은 자식(하위 노드)을 가질 때(=분기 계수가 높을 때) 탐색할 양이 많아져 하나만 쭉 파고 들어가는 DFS가 더 우월한 성능을 낼 수 있다.

 

[같은 뜻 비슷한 표현] 그래프의 간선이 많고(밀도가 높다/dense하다) 평균 인접 노드 수가 노드 수에 비해 높다면 너비 우선 검색은 긴 대기열을 가진다. 그에 비해 DFS는 적은 스택을 가지므로 DFS가 좀 더 성능이 좋을 것이다.)

따라서 분기 계수가 적은, 깊게 파고들어가지 않아도 되는 희소 그래프나 solution이 current node의 자식이 아닌 이웃 노드에 있을 것 같다면 BFS를 선택하자.

미주

분기 계수(branching factor)

각각의 노드가 가진 chilren을 정의하는 트리의 속성.즉 부모가 가지는 자식 노드의 수. (The branching factor is property of tree that defines the number of children at each node.)

희소 그래프(sparse graph)

간선이 얼마 없는 그래프 <-> 밀집 그래프: 간선(변)의 수가 최대간선의 수에 가까운 그래프.

reference dfs vs dfs 

https://www.andrew.cmu.edu/course/15-381-f09/hws/hw1/hwone_sol.pdfhttps://open4tech.com/bfs-vs-dfs/

 

(23. 10. 21 러프하게 작성)