[Algorithms] DFS, BFS, Dijkstra, Bellman-Ford, Floyd, Heap

DFS (Depth-First Search, 깊이 우선 탐색)

  - 방식 :

      - 모든 노드를 탐색 후 자신에게 돌아와야 끝난다.

      - 역추적(Backtracking) 과정이 있어 Stack / Recursion을 사용

      - 자기 자신을 호출하는 순환 알고리즘의 형태

  - 사용 예시

      - 미로 생성

      - Cycle Detection

      - Topological Sorting

  - 시간복잡도 (정점 N, 간선 E)

      - 인접 리스트로 표현된 그래프 O(N+E)

      - 인접 행렬로 표현된 그래프 O(N^2)

  - 장점

      - 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다.

      - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

  - 단점

      - 해가 없는 경로에 깊이 빠질 가능성이 있음. → 임의로 지정한 깊이까지만 탐색하도록 설정

 

BFS (Breath-First Search, 너비 우선 탐색)

  - 방식 

     - 모든 노드를 탐색 후 끝난다

     - 현재 연결된 모든 노드를 차례대로 탐색하기 위해 Queue를 사용

  - 사용 예시 

     - 두 노드 사이의 최단 경로(Shortest Paths)

     - 임의의 경로 탐색

     - 최소신장트리(Minimum Spanning Tree)

  - 시간복잡도 (정점 N, 간선 E)

      - 인접 리스트로 표현된 그래프 O(N+E)

      - 인접 행렬로 표현된 그래프 O(N^2)

  - 장점

      - 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 최단 경로를 찾을 수 있음

      - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

  - 단점

      - 경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 저장 공간의 수요가 매우 크다.

      - 해로 가는 경로들 모두가 같은 거리일 대 헛된 탐색

 

 

※※※※※※ V: Vertex, 정점, 노드

※※※※※※ E: Edge, 간선, 변

 

Dijkstra (시간복잡도 O((V+E)logV))

  - 그리디 알고리즘의 관점

  - 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘

    → A* 알고리즘이 Dijkstra의 확장된 알고리즘

  - 제약 사항

    - 그래프 내에 음의 가중치 합을 가지는 사이클이 없을 때에만 동작함

    - 음의 가중치를 갖는 간선이 없을 경우에만 아래의 시간복잡도에 동작함

      → 음의 가중치가 있을 경우 무한히 사이클을 돌며 거리가 작아지기 때문.

      → 다익스트라는 한 번 경로를 확정한 정점에 대해서는 다시는 갱신이 일어나지 않는다는 규칙이 있기 때문임.

  - Priority Queue와의 관계

    - 통상적인 시간 복잡도는 O(E+V^2) = O(V^2)

    - MinHeap을 이용하였을 때 시간 복잡도는 O((E+V)logV)

    → 이유는 MinHeap을 사용하면 logV만에 최소값이 가장 위로 정렬되기 때문임.

 

 

Bellman-Ford (시간복잡도 O(VE))

  - DP 관점

  - 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘

  - 다익스트라에서는 할 수 없었던 음의 가중치도 계산할 수 있음. 하지만 느림.

  - 전체 수행을 정점(N)보다 1만큼 작게 수행하도록 함.

 

Floyd Washall (시간복잡도 O(V^3))

  - 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘

  - 모든 정점에서 모든 정점으로의 최단 경로를 구하고자 하는 경우에 사용됨.

  - 사이클이 없는 경우 음수 가중치 처리가 가능함.

 

 

 

Heap (시간복잡도 O(logN))

  - 최대값 또는 최소값을 빠르게 찾기 위해서 고안된 트리 모양의 자료구조

  - max-heap : 부모 노드의 값이 자식 노드의 값보다 크다, 가장 큰 값을 빠르게 찾기 위한 것

  - min-heap : 부모 노드의 값이 자식 노드의 값보다 작다, 가장 작은 값을 빠르게 찾기 위한 것

  - 조건

    - Binary Heap은 완전이진트리 구조 이여야 한다.