다양한 그래프 이론 알고리즘

학기중 잠시 손을 놓고 있었던 알고리즘 문제를 풀다 보니 예전에 풀었고, 또 자료구조 수업을 수강할 때도 들었던 BFS/DFS같은 최단 경로 알고리즘도 기억이 나지 않아서
한번 여러 그래프 알고리즘들을 찾아보고 공부해보려고 한다.

알고리즘 문제에서 서로 다른 객체가 연결되어 있다? 라면 그래프 알고리즘일 가능성이 높다.

그래프 알고리즘

그래프는 주로 두가지 방식으로 구현된다.

1. 연결 리스트를 이용한 '인접 리스트' 방식

• 간선의 개수만큼 메모리가 필요로 하지만 인접 행렬에 비해서 O(v)의 시간복잡도를 가진다.

2. 2차원 배열을 이용하는 '인접 행렬' 방식

• 메모리 공간을 많이 필요로 하는 대신 노드간 간선의 비용을 구하는 시간이 O(1)의 시간복잡도를 가진다.

  그래프의 시간 복잡도와 공간 복잡도
  그래프를 분석할 때는 기존의 O(N)이용하지 않고 다른 알파벳으로 표현한다.

  1. V (Vertax)
     • 그래프 내에 있는 모든 노드들의 집합
  2. E (Edge)
     • 그래프 안에 있는 모든 간선들의 집합

  플로이드 워셜 / 다익스트라 알고리즘 - 추후 수정 예정

그래프 탐색 알고리즘

그래프 알고리즘의 기본인 DFS/BFS 알고리즘에 대해서 먼저 알아보자.

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

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
그래프에서 한 방향으로 탐색을 진행하다가 더 이상 탐색을 진행할 수 없는 상황이 되면, 가장 최근에 방문했던 정점에서 다시 탐색을 진행하는 방법이다.

동작과정은 이렇다.

1. 시작 노드를 스택에 Push()하고, 해당 노드를 방문했다고 기록한다.
2. 스택 최상단에 있는 노드를 기준으로 해당 노드와 연결되어 있는 노드 중 아직 방문하지 않은 노드가 있다면 해당 노드를 스택에 Push()하고, 방문 처리한다.
3. 2의 과정을 진행하다가 더 이상 방문할 인접 노드가 없는 경우 스택의 최상단 노드를 Pop() 하고 2를 진행한다.
4. 스택이 빌 때 까지 탐색한다. -> 모든 노드 탐색 완료

• 장점 : BFS에 비해서 낭비되는 메모리가 적다.
  찾아야 하는 노드가 깊게 있을수록, 또 좌측에 있을 수록 유리하다.
  
• 단점 : 경로가 매우 깊다면, 상대적으로 불리하다.
  탐색을 전부 수행하기 전에는 최단 경로라고 확신할 수 없다.

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

BFS는 깊이 우선 탐색과는 달리 노드v에 인접한 모든 노드를 방문한 다음
노드 v에 인접한 노드 중 하나를 다시 택하여 다시 너비 우선 탐색을 계속하는 방법이다.

1. 시작 노드를 큐에 삽입하고 방문 기록.
2. 큐에서 노드를 꺼내서 해당 노드의 인접 노드들 중 방문하지 않은 노드 모두를 큐에 삽입.
3. 2의 과정을 큐가 완전히 빌 때까지 반복한다.

• 장점 : 너비 우선 탐색이기 때문에 최단 경로를 보장한다.
  최단 경로가 존재한다면, 반드시 찾을 수 있다.
  노드 수가 적고 깊이가 얇을 때 유리하다.
• 단점 : DFS에 비해서 큐에 다음 탐색 노드들을 전부 저장하기 때문에 저장공간의 낭비가 있다.
  노드의 수가 늘어나면 탐색할 노드가 많아져서 비효율적이다.

특징	DFS	BFS
자료구조	스택, 재귀함수	큐
탐색 방식	깊이 우선	너비 우선
장점	깊고 왼쪽에 있는 경로일 수록 유리	노드 수가 적고 깊이가 얇을 때 유리

추가 예정(미완)