[알고리즘] DFS, BFS

1. DFS, BFS

그래프 탐색을 위해서는 DFS ( Depth-First Search, 깊이 우선 탐색 ), BFS ( Breadth-First Search, 너비 우선 탐색 ) 를 사용한다.

 

2. 그래프와 트리 비교

그래프는 노드와 노드를 잇는 (없을 수도 있지만) 간선을 가진 자료구조이며, 그 중 방향성이 있는 비순환 그래프가 트리이다.

 

3. DFS, BFS 시간복잡도

인접 리스트로 표현된 그래프 : O(N+E)

인접 행렬로 표현된 그래프 : O(N^2)

 

참고 : [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)