[1127] 자바 - Graph Traversal(그래프 탐색)

#그래프 탐색

- 그래프 탐색이란?

  ▪  그래프 탐색은 자료의 하나의 정점에서 시작해서 이어진 모든 정점들을 한 번식 방문하는 것이 목적이다.

  ▪  그래프의 데이터가 배열과 같이 일정한 열과 행을 가지며 정렬되어 있지 않기 때문에 찾고자 하는 자료를 찾을 때까지          모든 지점을 방문하여야 한다. 

  ▪ 그래프 탐색의 대표적인 방법에는 DFS, BFS가 있다

 

- BFS(Breadth-First Search)

  ▪ 너비 우선 탐색(BFS)는 가까운 정점부터 탐색한다.

  ▪ 더 탐색할 정점이 없는 경우 그 다음 떨어져 있는 정점을 순서대로 탐색한다.

  ▪ 주로 두 정점 사이 최단 경로를 찾을 때 사용한다.

너비 우선 탐색 BFS

  ▪ 위와 같은 그래프에서 BFS의 탐색 순서는 다음과 같다.

1. Start지점에서 가장 가까운 노드인 A~F를 탐색한다.
2. 탐색 후 그 다음 가까운 노드인 G와 같은 레벨의 노드들을 탐색한다. (S - A - G / S - B - H / S - C - I / S - D -T) 
3. 탐색 중 Target 노드를 발견하고 탐색을 종료한다.

 

- DFS(Depth-First Search)

  ▪ 깊이 우선 탐색(DFS)는 하나의 경로를 끝까지 탐색하여, 목적에 맞는 자료가 찾으면 종료된다.

  ▪ 목적에 맞는 정점에 도달하지 못하면 다음 경로를 탐색한다.

  ▪ 너비 우선 탐색(BFS)보다 탐색 시간이 더 소요될 수 있으나, 모든 노드를 완전히 탐색할 수 있다.

깊이 우선 탐색 - DFS

  ▪ 위와 같은 그래프에서 BFS의 탐색 순서는 다음과 같다.

1. Start지점에서 A 노드와 이하의 노드들을 끝까지 탐색한다. (S - A - G - K - G - M)
2. 탐색 후 그 다음 가까운 노드인 B, C의 노드를 A와 같은 방법으로 탐색한다. (B - H - N / C - I - T) 
3. 탐색 중 Target 노드를 발견하고 탐색을 종료한다.

 

- BFS와 DFS의 비교.

  ▪ 인접 행렬과 인접 리스트 (컴퓨터에서 그래프를 구현하는 방법) 

1. 인접 행렬
   두 정점을 바로 이어주는 간선의 표시가 2차원 배열로 만들어짐
   인접 행렬에서 행과 열은 정점을 의미하며, 각 원소는 정점간의 간선을 나타냄
2. 인접 리스트
   각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 만듬
   각 정점마다 하나의 리스트를 가지고 리스트에 인접한 다른 정점을 포함시킨다.

그래프 탐색	DFS	BFS
구현 방법	재귀 함수 / 스택	큐
수행 시간	느림	빠름
시간복잡도	인접 리스트: O(N + E) 인접 행렬: O(N^2)	인접 리스트: O(N + E) 인접 행렬: O(N^2)

 

  ▪ 동일한 시간복잡도를 가졌으나 실제 수행 시간의 차이는 구현 방법의 차이 때문이다.

  ▪ 일반적으로 재귀함수로 구현하는 DFS보다 큐로 구현하는 BFS가 조금 더 빠르게 동작한다.

  ▪ 그래프의 크기가 크다면 DFS를 사용, 크키가 작고 검색 대상과의 거리가 가깝다면 BFS를 사용하는 것이 유리.
  ▪ 경로의 특징을 고려해야한다면 DFS를 사용

  ▪ 최단 거리를 찾는 문제는 BFS를 사용