[TIL][Sat] BFS / DFS in Graph

2023. 10. 21. 20:39· 공부기록/Algorithm
목차
  1. DFS>BFS
  2. BFS>DFS
  3. 분기 계수가 왜 BFS와 DFS 성능 차이를 불러올까?
  4. 미주

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 러프하게 작성)

'공부기록 > Algorithm' 카테고리의 다른 글

[TIL][Wed] 최단거리 알고리즘_다익스트라/플로이드 워셜  (1) 2023.10.25
[TIL][Tue] 위상정렬 Topological Sorting  (1) 2023.10.24
[TIL][Fri] 스택 / 큐  (0) 2023.10.20
[TIL][TUE] 병합정렬/퀵정렬  (1) 2023.10.17
[TIL][Mon] 정렬  (2) 2023.10.16
  1. DFS>BFS
  2. BFS>DFS
  3. 분기 계수가 왜 BFS와 DFS 성능 차이를 불러올까?
  4. 미주
'공부기록/Algorithm' 카테고리의 다른 글
  • [TIL][Wed] 최단거리 알고리즘_다익스트라/플로이드 워셜
  • [TIL][Tue] 위상정렬 Topological Sorting
  • [TIL][Fri] 스택 / 큐
  • [TIL][TUE] 병합정렬/퀵정렬
J융
J융
Recording of development
J융
Develop day by day
J융
전체
오늘
어제
  • 분류 전체보기 (67)
    • 공부기록 (63)
      • CS (8)
      • OS (15)
      • Algorithm (19)
      • Web (3)
      • HTML&CSS (6)
      • Electron (1)
      • JavaScript (5)
      • Network (0)
      • C (2)
      • Python (3)
      • Git (1)
    • 개발일기 (3)
      • Alice기록 (0)
      • Krafton Jungle 기록 (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • pintos
  • #cs기초
  • 크래프톤정글
  • JS기초
  • 앨리스트랙
  • 수강후기
  • os
  • 정글공부키워드
  • 엘리스AI트랙
  • Web
  • CG
  • cs기초
  • 알고리즘
  • 기술면접대비
  • 비전공자개발자
  • 부트캠프
  • cs지식
  • vm
  • 개발일기
  • fe

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
J융
[TIL][Sat] BFS / DFS in Graph
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.