그래프 탐색

• 깊이 우선 탐색(Depth First Search : DFS)
  • 한 정점으로부터 연결된 한 정점으로만 탐색하여 끝까지 탐색하는 방법
  • 한 정점에서 연결된 정점을 찾아 해당 정점으로 이동
  • 만약 연결된 정점이 없다면 이전 정점으로 이동해 다른 정점 탐색
  • 모든 정점에 대해서 탐색이 이루어진다
  • 구현 방법
    • Stack
      • 현재 정점에 연결된 다른 정점을 찾을 시 돌아갈 정점, 즉 현재 정점을 스택에 저장
      • 현재 정점에서 연결할 정점이 없어면 스택에서 다시 정점을 빼서 수행
    • 재귀로도 구현 가능
      • 현재 정점에 연결된 다른 정점이 있다면 다시 재귀 호출
      • 현재 정점에서 연결할 정점이 없다면 해당 재귀 탈출
  • 시간 복잡도
    • O(V+E)
• 너비 우선 탐색(Breadth First Search : BFS)
  • 한 정점에 연결된 모든 정점을 모두 탐색
  • 트리에서의 레벨순회 처럼 현재 정점을 기준으로 연결된 모든 정점을 탐색
  • 구현방법
    • Queue
      • 탐색할 정점을 순서대로 빼기 위해 큐를 사용 
      • 현재 정점에서 연결된 다른 정점을 큐에 넣는다
      • 현재 정점 탐색이 끝나면 큐에서 다음 정점을 빼서 위의 과정을 반복한다
      • 큐를 활용하여 먼저 탐색한 순서대로 방문을 하기 때문에 가중치가 1인 그래프에서 최단 거리로 이동이 가능
  • 시간 복잡도
    • O(V+E)