탐색

다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘(Dijkstra's algorithm)은 벨만-포드 알고리즘처럼 특정한 노드에서 시작하여 그래프의 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라는 벨만-포드 알고리즘에 비해 좀 더 효율적이기 때문에 그래프가 큰 경우에도 사용할 수 있다는 장점이 있다. 하지만, 이 알고리즘은 음수인 가중치를 가진 간선이 있는 경우에는 사용할 수 없다는 단점이 있다. 다익스트라 알고리즘도 벨만-포드 알고리즘처럼 각 노드까지의 거리를 저장하고 탐색 과정에서 값을 줄여나간다. 각 단계에서는 아직 처리하지 않는 노드 중 거리가 가장 작은 노드를 찾고, 그 노드에서 시작하는 모든 간선을 쭉 살펴보며 노드까지의 거리를 줄일 수 있다면 줄인..

깊이 우선 탐색 (Depth-First Search, DFS) 깊이 우선 탐색은 직관적인 그래프 순회 방식이다. 임의의 시작 노드를 설정하고 간선을 따라 이동해 가며 도달 가능한 모든 노드를 처리한다. 더 이상 갈 수 없는 노드까지 탐색한 후, 이전노드로 돌아가 그래프의 다른 부분을 탐색하기 시작한다. 방문했던 노드를 기록하므로 각 노드는 한 번씩만 처리된다. 1번 노드를 시작으로 정하고, 더 이상 갈 수 없을 때까지 순회한다. 즉 1 -> 2 -> 3 -> 5 순으로 방문한 뒤, 다시 1번 노드로 돌아간다. ( 2번 노드는 이미 방문한 노드이기 때문에 다시 방문하지 않는다. ) 그런 다음 방문하지 않는 노드인 4번 노드를 방문한다. DFS 구현 import java.util.ArrayList; impo..