길찾기 알고리즘에는 DFS, BFS, 다익스트라 알고리즘 등이 있다.
1. DFS(Depth First Search)
DFS는 깊이 우선 탐색이라고 하며, 어떠한 그래프를 탐색할 때 최대한 깊숙히 탐색을 한 후, 더 탐색 할 수 없으면 다른 경로를 탐색하는 알고리즘입니다.
DFS의 순회 과정
예시)
A -> B -> D
1) A와 연결된 노드는 B와 C입니다. 두 개 중 무엇을 선택해도 상관은 없습니다.
그림에 상에서 가장 위쪽의 노드인 B를 선택하도록 하였습니다.
2) B와 연결된 노드 중 B보다 깊이가 깊은 노드는 D, E
가장 위쪽의 노드인 D선택
B -> E -> G
3) D와 연결된 노드 중 D보다 깊은 노드는 없습니다. 다시 B로 돌아갑니다.
4) B와 연결된 노드 중 B보다 깊이가 깊으며 아직 탐색하지 않은 노드는 E, E 선택
5) E와 연결된 노드 중 E보다 깊이가 깊으며 아직 탐색하지 않는 노드는 F,G
가장 위쪽의 노드인 G선택
E -> F
6) G와 연결된 노드 중 G보다 깊은 노드는 없습니다.
다시 E로 돌아갑니다.
7) E와 연결된 노드 중 E보다 깊이가 깊으며 아직 탐색하지 않은 노드는 F
F 선택
A -> C
8) F와 연결된 노드 중 F보다 깊이가 깊으며 아직 탐색하지 않은 노드는 없습니다.
F에서 더 깊이 탐색을 하려고 해도 깊이가 더 깊은 노드가 없기 때문에
다시 E로 돌아옵니다.
9) E와 연결된 노드 중 아직 탐색을 하지 않은 노드는 없습니다.
다시 B로 돌아옵니다.
10) B와 연결된 노드 중 아직 탐색을 하지 않은 노드는 없습니다.
다시 A로 돌아옵니다.
11) A와 연결된 노드 중 A보다 깊이가 깊으며 아직 탐색하지 않은 노드는 C입니다.
C를 선택
2.BFS(Breadth First Search)
BFS는 너비 우선 탐색이라고 하며, 그래프를 탐색할 때 갚은 깊이에 해당하는 노드부터 탐색하고 더 탐색할 수 없으면 더 깊은 노드들을 탐색하는 알고리즘입니다.
BFS의 순회 과정
예시)
1) A와 연결된 노드는 B와 C. 둘 중 아무거나 선택. 가장 위쪽의 노드를 선택
B 선택
2) B와 같은 깊이에 해당하는 노드는 C
C 선택
3) C와 같은 깊이에 해당하는 노드 중 탐색하지 않는 노드가 없습니다.
더 깊은 곳을 탐색합니다.
4) 다음 깊이에 해당하는 노드는 D,E,F. 가장 위쪽 노드인 D부터 탐색
D 선택
5) D와 갚은 깊이에 해당하는 노드는 E, F 입니다. 위쪽 노드는 E부터 탐색
E 선택
6) 남는 노드인 F 선택
F 선택
7) F와 같은 깊이에 해당하는 노드 중 탐색하지 않은 노드가 없다.
더 깊은 곳을 탐색합니다.
8) 다음 깊이에 해당하는 노드는 G입니다.
G 선택
3.Dijkstra(다익스트라 최단 경로 알고리즘)
다익스트라 알고리즘은 그래프의 탐색 알고리즘으로 가중치가 있는 그래프의 최단 경로를 구할 때 사용된다.
다익스트라 알고리즘은 BFS와 유사하며, 노드 사이 간선(Edge)에 양의 가중치를 갖는 그래프(음의 가중치 허용X)에서 최단 경로를 찾을 때 사용합니다.
여기서 가중치란 그 지점까지의 거리라고 보면 됩니다.
