BFS(너비우선탐색) - 최단 경로 문제를 푸는 알고리즘

최단경로,즉 가장 짧은 것을 찾는 문제.

 

예를 들어

여러분이 친구 집까지 가는 최단 경로일 수도 있고, 

체스 게임에서 체크 메이트를 만드는 데 필요한 최소한의 수 일수도 있습니다.

 

이렇게 최단 경로 문제를 푸는 알고리즘을 너비 우선 탐색이라고 합니다.

 

문제를 풀기 위해선 다음과 같은 절차가 필요합니다.

1. 문제를 그래프로 모형화한다
2. 너비 우선 탐색으로 문제를 푼다

너비 우선 탐색은 다음과 같은 두 가지 종류의 질문에 대답하는 데 도움이 됩니다.

 

유형 1. 정점A에서 정점B 로 가는 경로가 존재하는가?

유형 2. 정점A에서 정점B로 가는 최단 경로는 무엇인가?

---

BFS는 Queue를 이용합니다.

망고 판매상을 찾는다고 가정할 경우 나->1촌->2촌->3촌->...

1촌관계인 모든 사람중에서 찾는다 -> 목록에 2촌을 추가한다 -> 2촌의 모든사람중에서 찾는다->...

이렇게 탐색하면 최단 경로를 찾을 수 있다.

대신, 목록에 더해진 순서대로 사람을 탐색해야 한다

-> 큐(Queue)를 이용해야 한다!

---

그래프의 구현

 

파이썬 코드는 해시테이블 이용

자바는...? HashMap으로 이용할 수 있으나 대부분의 실용적인 연산에서는 인접리스트를 이용한 방법이 더 효율적입니다.

 

Why?  HashMap의 시간복잡도는 O(1)이 아니다. (충돌 발생할 경우 있음) -> 인접리스트가 조회시 더 빠르다.

 

java로 그래프를 구현하는 방법은 주로 인접행렬, 인접리스트 를 이용해서 구현하는 2가지 방법이 있습니다.

 

n개의 정점, e개의 간선을 가지는 그래프인 경우 비교

인접행렬	인접리스트
2차원 배열 사용	연결 리스트를 사용
두 정점을 연결하는 간선의 존재 여부 : O(1)	두 정점을 연결하는 간선의 존재 여부: O(n)
정점의 차수(인접 행렬의 행, 열을 조사) : O(n)	정점의 차수(인접 행렬의 행, 열을 조사) : O(n)
그래프에 존재하는 모든 간선의 수: O(n제곱)	그래프에 존재하는 모든 간선의 수: O(n+e) : 큐 추가+리스트탐색
어떤 노드의 인접 노드를 찾을 때 비효율적이다. 노드의 수가 많을수록 메모리를 많이 차지한다.	노드 간 연결 여부 확인 시 비효율적이다

그래프를 탐색하는 것은 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

따라서 DFS,BFS의 시간복잡도는 모든 간선의 수를 찾는 시간 복잡도와 같음.

 

간선이 많은 그래프인 경우 인접 행렬을 통해 빠르게 연결 여부 확인 가능.

간선이 적은 그래프인 경우 인접리스트를 통해 인접 노드를 빠르게 확인 가능

 

 

* Graph를 인접리스트로 구현시 LinkedList보다 ArrayList를 주로 사용하는 이유? 노드에 빠르게 접근하고 삽입 삭제작업이 빈번하지 않다면 ArrayList가 효율적이다.(내부적으로 배열을 사용하여 빠르게 접근 가능,캐시 활용 효율적)

 

알고리즘의 구현

1. 확인할 사람의 명단을 넣을 큐를 준비한다
2. 확인한 사람을 표시하는 배열을 만든다(무한 반복 방지)
3. 큐에서 한 사람을 꺼낸다
4. 이사람이 확인한 적이 있는지 확인한다
5. 이사람이 망고 판매상인지 확인한다
6. 예)-> 작업 완료 / 아니오)-> 그 사람의 이웃을 모두 큐에 추가한다
7. 확인하고 나서 확인했다고 표시한다
8. 반복
9. 만약 큐가 비어있으면 네트워크에는 망고 판매상이 없다

 

 

참고 도서: 그림으로 개념을 이해하는 알고리즘 - 아디트야 바르가바