그래프

그래프란 연결의 집합을 모형화 한 것이다.

그래프는 정점(node) 과 간선(edge)로 이루어져 있는데, 정점은 여러 개의 다른 정점과 바로 이어질 수 있다. 이렇게 바로 이어진 정점을 이웃이라고 한다. 그래서 2는 1의 이웃이다.

너비 우선 탐색

최단 경로 문제를 푸는 알고리즘 이다.

최단 경로?

최단경로를 정리 하자면 두가지 질문에 대해 대답할수 있다.
1. 정점 a에서 정점 b로 가는 경로가 존재 하는가?
2. 정점 a에서 정점 b로 가는 최단 경로는 무엇인가?

queue

큐(대기열) 는 큐 안의 원소에 임의로 접근할수 없는데, 삽입과 제거와 같은 연산을 사용한다.

그래프의 구현

그래프 표현은 해시 테이블로 할수 있다!

해시 테이블을 사용하면 키에 값을 할당 할수 있는데 이런 경우에는 어떤 정점에 이웃하는 정점을 할당 하면 된다.

예를 들면 아래의 코드와 같다.

let graph = {};
graph["I"] = ["alice", "bob", "claire"];

알고리즘의 구현

알고리즘이 구현되는 방식은 다음과 같다

1. 확인할 사람의 명단을 넣을 큐를 준비한다.
2. 큐에서 한사람을 꺼낸다
3. 해당 사람이 조건에 충족한지 확인한다
4. YES? 작업완료 | NO? 그사람의 이웃을 모두 큐에 추가한다.
5. 2번을 반복한다.
6. 만약 큐가 비어 있다면 그래프에는 조건에 충족하는 사람이 없다.

큐를 갱신할 때 push와 pop을 사용하는 것이다!

자바스크립트의 Deque 를 정리한 내용

요약

• 너비 우선 탐색은 a에서 b로 가는 경로가 있는지 알려준다.
• 만약 경로가 존재한다면 최단 경로도 찾아준다.
• 만약 x까지의 최단 경로를 찾는 문제가 있다면 그문제를 그래프로 모형화 해본후 너비 우선 탬색으로 문제를 푼다.
• 방향 그래프는 화살표를 가지며, 화살표 방향으로 관계를 가진다.
• 무방향 그래픈느 화살표가 없고, 둘 간의 상호 관계를 나타낸다.
• 큐는 선입선출이다.
• 스택은 후입 선출이다.
• 탐색 몰고에 추가된 순서대로 사람을 확인해야 한다. 그래서 탐색 목록은 큐가 되어야 한다. 그렇지 않으면 최단 경로는 구할 수 없다.
• 누군가를 확인한 다음에는 두번다시 확인하지 않도록 해야한다. 그렇지 않으면 무한 반복이 되어 버릴 수 있기 때문이다.

---

참고

'Hello Coding 알고리즘' 책을 공부하여 요약정리한 내용입니다.