dfs2 DFS, BFS with Java 우선 간단하게 BFS와 DFS의 정의를 살펴보고 예제를 설명해보겠습니다. BFS는 너비 우선 탐색이라고 합니다. 너비 우선 탐색은 시작 정점에서 인접한 정점들을 우선적으로 방문하는 탐색 방법입니다. 그림을 보면서 너비 우선 탐색이 어떻게 탐색을 진행하는지 알아보겠습니다. 시작 정점은 A 입니다.A에서 인접한 정점은 B, C, D가 있네요. B부터 차례대로 방문 합니다. B에 방문했다면 해당 정점에서 인접한 정점이 있는지 확인합니다. B는 E와 F가 연결되어 있네요. 이 때, E와 F에 바로 방문하는 것이 아닙니다. 우리는 A에서 인접한 정점 B, C, D 를 우선적으로 방문한 뒤 E, F에 방문해야 합니다. 일단 나중에 방문하기로 하고 Queue에 저장합니다. B를 방문한 뒤 C를 방문합니다. C에서도 .. 2022. 9. 14. 다익스트라(Dijkstra) 알고리즘 with Java 다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 단 한개의 음의 가중치라도 허용되지 않으며, 만약 음의 가중치가 있는 그래프라면 다익스트라 알고리즘 대신 벨맨 포드 알고리즘을 사용하는 방법이 있습니다. 구현방법 다익스트라 알고리즘을 구현하는 방법에는 반복 문을 사용하는 방법과 우선순위 큐를 사용하는 방법이 존재합니다. 현재 포스팅에서는 이해가 쉬운 반복문을 사용하는 방법을 배운 뒤 이를 응용하여 우선순위 큐로 구현하는 법으로 넘어가겠습니다 :) 구현 길이를 저장할 배열과, 해당 노드에 방문했는지 확인할 배열이 필요합니다. 이 예제에서는 dist, ch 라고 이름을 붙히겠습니다. dist와 ch 배열의 크기는 노드의 개수로.. 2022. 9. 14. 이전 1 다음
