[그래프] 그래프 탐색, DFS, BFS

앞의 글에서 푼 백준 1012번이 그래프, DFS였음 

뭔지도 모르고 풀었나 심각함 하지만 이젠 알아야 함

 

마침 2-2 알고리즘 강의 ppt가 있음

그래프 표현

• 정점 개수 E 간선 개수 V
• 공간 복잡도 
  • 인접 리스트 (Adjacency-list)
    • directed graph, undirected graph 모두 공간 복잡도 Θ(E+V)
      
  • 인접 행렬 (Adjacency-matrix)
    • directed graph, undirected graph 모두 공간 복잡도 Θ(V^2)

 

 

• 그래프가 sparse하다면, 간선의 개수가 적다면 인접 리스트가 더 나음
• 그래프가 dense하다면, 간선의 개수가 많다면 인접 행렬이 더 나음
• 모든 정점을 방문하는 데 시간 복잡도
  • 인접 리스트: Θ(E+V) -> 더 효율적
  • 인접 행렬: Θ(V^2)

BFS(Breadth-first search), 너비 우선 탐색

• 시작점에서 닿을 수 있으면 한 칸씩 옆으로 갔다가 아래로 갔다가 넓게넓게 가보는 거지

탐색 순서, s에서 시작

강의 자료 내 pseudo code

• 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