[자료구조 - 그래프의 순환] 코딩 테스트의 꽃 그래프의 순환 BFS와 DFS

그래프는 비선형 자료구조이기 때문에 배열처럼 단순한 반복으로 그래프를 조회하는 것은 비효율적이다.

그래프는 각 정점 간의 연결 관계를 사용해 조회하는 방법을 사용한다.(한 정점에서 연결된 다른 정점으로 이동하며 조회한다.)

• 깊이 우선 탐색(Depth First Search)
• 너비 우선 탐색(Breadth First Search)

---

[깊이 우선 탐색 - DFS]

깊이 우선 탐색이란? 하나의 경로로부터 도달할 수 있는 모든 노드를 방문한 이후 다른 경로를 조회하는 방법이다.

• 한 노드로부터 발생하는 모든 경로를 탐색할 때까지 해당 노드 정보는 유지한다.
  • 모든 경우의 수를 검사하거나, 규칙이 복잡한 경로를 탐색할 때 유리하다.
  • 현재 정점에서 갈 수 있는 점들 중 한 곳을 우선적으로 끝까지 탐색한다.
• 한 번에 하나의 경로만을 조회하게 된다.
  • 각 경로의 고유 정보를 저장해두기에 유리하다.
• 스택이나 재귀 함수를 이용해서 구현한다.
• 각 노드는 DFS 방문 순서에 따라 다양한 성질을 가지기 때문에 다양하게 활용할 수 있다.
• 탐색의 우선 순위를 제어하기 쉽다.
• BFS에 비해 메모리 사용이 적고 속도가 빠르다. 그러나 최적해는 찾지 못한다.

 

[DFS의 정렬]

연결 트리를 DFS로 탐색하는 과정에서 각 정점에 다양한 기준으로 번호를 부여한다.

• In-Order, Pre-Order, Post-Order Numbering

탐색 과정에서 각 정점을 DFS에서의 탐색 기준에 따라 Tree모양으로 전개할 수 있다.

• 이를 DFS Tree라 하며, 그래프의 다양한 특징을 쉽게 판별할 수 있게 해 준다.

---

[너비 우선 탐색 - BFS]

너비 우선 탐색은 출발 노드로부터 가까운 노드들부터 차례로 탐색하는 방식이다.

• 현재 정점에 연결된 가까운 점들로부터 탐색을 한다.
• 같은 탐색 깊이(거리)를 가진 모든 노드들을 조회한 이후에 다음 깊이를 조회한다.
• 탐색 순서가 일관되게 유지된다.
• 큐를 사용하여 구현한다.
• 동시에 여러 경로를 탐색할 수 있다.
• DFS보다 메모리 사용이 많고 속도가 느리다. 그러나 최적해를 찾기가 좋아 최단 거리 찾기에 사용된다.

 

[BFS의 최단경로]

가중치 그래프 G(V, E)의 두 정점 u, v에 대해  "u에서 v로의 최단 경로"는 다음과 같이 정의한다.

• 정점 u 에서 정점 v로 가는 단순 경로들 중 가중치의 합이 최소가 되는 간선 집합
• f(G) = { s -> c, c -> f, f -> e, e -> f)

일반적으로 BFS는 Depth(거쳐온 간선의 수)가 작은 순서대로 정점을 방문한다.

그렇기에 모든 가중치가 1인 비가중치 그래프에서는 항상 가까운 정점부터 방문함을 보장할 수 있다.

그러나, 가중치 그래프에서는 Depth와 가중치 합이 비례함을 보장할 수 없다.

BFS의 최단거리를 계산하는 다양한 알고리즘

1. Dijkstra Algorithm(다익스트라)
2. A-Star Algorithm(에이스타)
3. Bellman-Form Algorithm
4. Floyd Warshall Algorithm

 

그중, Dijkstra Algorithm의 기본 스택

1. 출발 정점을 Queue에 삽입한다.
2. int D[] = { .... }
3. Queue가 모두 비어질 때 까지 다음을 반복한다.
   1. Queue에 있는 정점들 중 출발점으로부터의 누적거리가 가장 작은 정점 v를 뽑는다.
   2. v가 이미 D[v]가 계산 완료된 정점이라면 continue;
   3. D[v]를 갱신한다
   4. V와 인접한 모든 정점 u에 대해
      1. D[u] > D[v] + ||v->u||라면 Queue에 정점 u를 삽입한다.
4. 위 과정을 반복한 후 모든 정점 v에 대한 정점 s로부터 최단거리 D[v]가 저장된다.

 

A-Start Algorithm의 기본 스택

A*알고리즘은 시작 노드에서 도착 노드까지 추정되는 전체비용을 최소로 하는 노드를 찾고 확장해 나가는 알고리즘이다.

1. 시작 노드에 검색된 인접 노드들을 열린 목록에 넣는다. 열린 목록은 최단 경로를 분석하기 위한 상태값들이 계속 갱신되며, 닫힌 목록은 처리가 완료된 노드들을 담아둔다.
2. Queue가 모두 비어질 때까지 다음의 과정을 반복한다
   1. 열린목록에서 가장 낮은 비용 F를 찾아 현재 노드에 넣는다.
   2. 이 F를 열린 목록에서 꺼내 닫힌 목록에 넣는다.
   3. 선택한 노드에 인접한 8개의 노드에 대해 탐색을 시도한다. 만약 인접한 노드가 닫힌 목록상에 있다면 무시를 하고, 그렇지 않다면 아래 내용을 반복한다.
      1. 인접한 노드가 열린 목록에 존재하지 않다면, 이를 열린 목록에 추가하고 이 노드를 현재 노드로 만든다. 노드의 각각 F(최소 비용) = G(지불할 비용) + H(남은 비용)을 기록한다.
      2. 인접한 노드가 열린 목록에 존자한다면, G비용을 비교해 가며 최적의 노드를 현재 노드로 만든다. 그 노드의 각각 F, G, H의 비용을 계산한다.
3. 길을 찾던 중 목표 노드이 열린 목록에 추가되었을 때, 혹은 열린 목록(Queue)이 비어있게 될 경우 멈춘다.

Bellman Ford Algorithm의 기본 스택

1. int[] D = {....}
2. 출발 정점 S에 대해 D[s] = 0
3. 아래 과정을 최대 V번 반복한다.
   1. updated = false;
   2. 모든 노드 u에 대해 차례로 (u와 인접한 모든  노드 x에 대해 차례로)
      1. D[x] < D[u] + ||u->x||로 갱신한다.
      2. updated = true;
4. 3번 과정이 V번 이상 반복되었다면 Negative Cycle이 존재한다.
5. 그렇지 않다면 D[]는 각 정점에 대한 최단 거리 배열이 된다.