코테준비
[그래프] 그래프 탐색, DFS, BFS
anstjwls
2024. 3. 8. 11:32
앞의 글에서 푼 백준 1012번이 그래프, DFS였음
뭔지도 모르고 풀었나 심각함 하지만 이젠 알아야 함
마침 2-2 알고리즘 강의 ppt가 있음
그래프 표현
- 정점 개수 E 간선 개수 V
- 공간 복잡도
- 인접 리스트 (Adjacency-list)
- directed graph, undirected graph 모두 공간 복잡도 Θ(E+V)
- directed graph, undirected graph 모두 공간 복잡도 Θ(E+V)
- 인접 행렬 (Adjacency-matrix)
- directed graph, undirected graph 모두 공간 복잡도 Θ(V^2)
- 인접 리스트 (Adjacency-list)
- 그래프가 sparse하다면, 간선의 개수가 적다면 인접 리스트가 더 나음
- 그래프가 dense하다면, 간선의 개수가 많다면 인접 행렬이 더 나음
- 모든 정점을 방문하는 데 시간 복잡도
- 인접 리스트: Θ(E+V) -> 더 효율적
- 인접 행렬: Θ(V^2)
BFS(Breadth-first search), 너비 우선 탐색
- 시작점에서 닿을 수 있으면 한 칸씩 옆으로 갔다가 아래로 갔다가 넓게넓게 가보는 거지
- 1-9 line : Initialization : O(V)
- 10-18 line : Graph Exploration : O(V+E)
- 11, 18 line → O(V)
- 12-17 line → O(E)
- vertex is examined at most once
- edge is explored at most twice(undirected), once(directed)
- Overall : O(V+E)
DFS (Depth-first search), 깊이 우선 탐색
- 시작점에서 연결된 정점은 연결이 끊길 때까지 파고들어감, 연결이 끊기면 그 때 다음 정점으로 넘어가
- 각 정점의 색
- 초기 흰색
- 방문(visited)하면 -> 회색
- finished(해당 정점의 인접 리스트가 모두 방문되면) -> 검은색
- 방문시점/finished 시점으로 숫자 표시
- 탐색 종료 시
- pseudo code