반응형
d
| DFS | BFS |
| Depth First Search | Breadth First Search |
| Stack / Recursive | Queue |
 |
 |
Time Complexity:
- 인접 리스트로 표현된 그래프
O(N+E)
- 인접 행렬로 표현된 그래프
O(N^2)
N is the number of nodes in the graph,
E is the number of edges
adjacent matrix
dfs 시간 복잡도
dfs(x)는 x에 방문하는 함수이므로 정점의 개수, 즉 차수인 V번만큼 dfs(x)가 호출됩니다. 따라서 dfs(x) 시간복잡도 *V가 전체 dfs 알고리즘의 시간복잡도가 됩니다.
- 인접 행렬로 표현된 그래프
모든 정점을 다 찾아봐야하기 때문에 dfs(x)의 시간복잡도는 O(N)
dfs(x)가 N번 호출되어야 하므로 전체 dfs 알고리즘의 시간복잡도는 O(N*N)=O(N^2)
- 인접리스트로 표현된 그래프
인접 행렬과 마찬가지로 dfs(x)는 N번 호출
dfs(x)의 시간복잡도는 O(N+E)
인접리스트에서 dfs가 호출되는 방법은 모든 정점을 다 찾는 인접행렬의 탐색방법과 다릅니다. 또한 a[x].size()는 전체 간선의 개수가 아니라, 한 정점과 연결된 간선의 개수이기 때문에 dfs(x)의 시간복잡도는 O(E)가 아님을 주의해야 합니다.
반응형