다익스트라와 BFS

  • 알고리즘을 풀때 자주 사용하는 두가지 개념에 대해 한번 더 정리해보자.
  • 그저 둘이 비슷하다 생각하지만 목적을 좀더 명확하게 정리한다.

두개의 개념

BFS

  • BFS는 너비 우선 탐색 Breadth First Search
  • 그래프의 탐색 기법중 하나.
    • 비선형 구조인 그래프로 표현된 모든 정점을 빠짐없이 탐색 한다.

Daijkstra

  • 다익스트라는 최단 경로 탐색 알고리즘
  • 하나의 정점으로부터 다른 정점까지의 최단거리를 구할 수 있다.

정리하자면?

  • 둘을 비슷하게 생각하고 구현할때에도 같은 개념처럼 사용한다.
    • 앗 이건 최단거리 구하는 문제다! -> BFS면 럭키비키자나~
    • 하지만 구현한것은 Daijkstra이다.
  • 개념으로 따지면 Daijkstra에 BFS개념이 들어간 것으로 생각해야 한다.
    • BFS > Daijkstra느낌
    • 최단 거리를 구하는데 BFS를 사용해서 효율적으로 만든것이다.
  • 좀더 자세한 차이점을 알아보자.

시간 복잡도

  • BFS의 경우엔 모든 점점(V)과 간선(E)을 확인하기 때문에 O(V+E)의 시간 복잡도를 가진다.
    • 그저 정점에 방문했냐만 확인하고 간선을 선택하는 방식으로 모든 정점을 순회한다.
    • 순서자체가 기준이 되는 정점으로 부터 같은 거리의 정점을 먼저 탐색하는 방식
  • 다익스트라는 O(ElogE)의 시간 복잡도를 가진다.
    • 어째서? 구현되는 과정 자체를 보면 그리디와 같은 방식으로 탐색을 진행한다.
    • 첫 정점에서 연결된 모든 간선들을 확인하고 갱신한다.
    • 최단 거리라고 계산된 또다른 정점으로 부터 다시 모든 간선들을 확인하고 갱신한다.
      • 이런 방식으로 A-B가 먼저 거리 계산이 되더라도 A-C-F-B가 낮은 거리를 가진다면 갱신하게 된다.
    • 이런 과정을 빠르게 계산하기 위해 우선순위 큐가 사용된다.
      • 누적된 거리를 기준으로 정렬된 우선순위큐!
      • 그럼 모든간선(E) 들을 우선순위 큐에 넣게 되고, 우선순위 큐는 힙의 구조로 정렬이 logE가 걸리므로 O(ELogE)가 되게 된다.
  • 구현자체의 차이가 있기 때문에 위와 같은 시간 복잡도에서 차이가 난다는점을 알아가자.

그래프의 형태

  • BFS는 그래프의 가중치가 없거나, 가중치가 음이든 양이든 상관 없이 작동한다.
    • 그저 그래프를 동일 너비(레벨)별로 탐색하기 위해 사용되는 알고리즘이기 때문
    • 그래서 BFS가 무조건 최단거리를 보장한다고 할 수 없다는 것이다.
  • Daijkstra는 그래프의 가중치가 0이상의 양의 정수여야 작동한다.
    • 특정 정점으로부터 시작해 최단 거리를 구하는 것이므로 0이 상의 가중치를 간선마다 가지고 있어야 한다.

마무리

  • BFS와 다익스트라를 혼동해서 사용하게 되서 정리를 진행해 보았다.
  • 한마디로 두개념을 정리하기는 장황하다고 생각한다.
  • 결국 한마디로 정리해보면
    • BFS는 모든 정점을 탐색하는데 사용하는 알고리즘으로 큐를 이용해 구현을 한다. 한 정점에서 같은 레벨별로 탐색이 되며 무 가중치 그래프에서 연결성분을 찾거나, 최단 경로 탐색을 하는데 사용할 수 있다.
    • 다익스트라는 한 정점에서 다른 정점간의 최단 거리를 찾는 알고리즘으로 우선순위큐를 이용해 구현이 된다. 그리디한 방식을 통해 구현이 되며 양의 가중치를 가진 그래프에서 최적의 경로를 찾을 때 사용한다.
  • BFS는 좀더 간단한 탐색에 사용(가중치가 없는 간선수가 적은 경로 찾기) 다익스트라는 양의 가중치가 있는 최적의 경로를 찾을때 사용한다.