그래프 탐색 -BFS, DFS

그래프 탐색 (그래프 순회)

하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것

BFS

너비 우선 탐색

• 시작 노드를 방문 표시 후 큐에 넣음
• 큐에 아무노드가 없을때까지:
  • 큐 가장 앞 노드를 꺼낸다.
  • 꺼낸노드에 인접한 노드들을 모두 보면서:
    • 처음 방문한 노드면:
      • 방문한 노드 표시를 해준다
      • 큐에 넣어준다.

BFS 알고리즘 시간 복잡도

1. BFS 노드 전처리 → O(V)
2. 큐에 노드를 넣고 빼는데 걸리는 시간 → O(V)
3. 큐에서뺀 노드의 인접한 노드들을 도는데 걸리는 시간 →O(E)

⇒총 O(2V+E) ⇒ O(V+E)

DFS

깊이 우선 탐색

• 시작 노드를 옅은 회색 표시후, 스택에 넣음
• 스택에 아무 노드가 없을때까지 :
  • 스택 가장 위노드를 꺼낸다.
  • 노드를 방문 표시를 한다.
  • 인접한 노드들을 모두 보면서:
    • 처음 방문하거나 스택에 없는 노드면 :
      • 옅은 회색 표시를 해준다.
      • 스택에 넣어준다.

DFS 알고리즘 시간 복잡도

1. DFS 노드 전처리 → O(V)
2. 스택에 노드를 넣고 빼는데 걸리는 시간 → O(V)
3. 스택에서 뺀 노드들의 인접한 노드들을 도는데 걸리는 시간 →O(E)

⇒ 총 O(2V+E) ⇒ O(V+E)