반응형 개발/문제풀이7 깊이 우선 탐색(Depth First Search : DFS) 알고리즘 자바로 구현하기 - 깊이 우선 탐색(Depth First Search, DFS)이란? 시작점 v부터 인접한 정점 중에 방문하지 않은 정점 w를 방문하고 다시 w로부터 탐색을 시작합니다. 그 후 어떤 정점 u를 방문하고 u에 인접한 모든 정점들을 이미 방문한 경우에는 그 전에 마지막으로 방문한 정점으로 되돌아가서 위의 과정들을 반복합니다. 모든 정점들을 방문한 후 탐색을 종료합니다. DFS 결과는 1->2->4->8->5->6->3->7입니다. 필요한 변수 - 정점의 passing여부를 나타내는 vertex 집합 - 정점의 연결 여부를 나타내는 c 집합 - 지나온 정점을 저장하는 p 집합 핵심 인접한 정점은 1을 기준으로 할 때 2,3이 인접해 있으나 2로 먼저 이동한다고 가정하고 문제를 풀어야 합니다. 두개의 정점이 연.. 2017. 11. 10. 순회판매원 문제 자바로 구현하기 순회판매원 문제 알고리즘은 헤밀턴 순회의 응용문제입니다. * 헤밀턴 순회란? 출발점으로부터 모든 정점을 한번씩만 지나서 출발점으로 돌아오는 순회를 의미합니다. 순회판매원 문제는 판매원이 각 도시를 한 번만 방문하여 출발점으로 되돌아오는 최소 경로를 구해야합니다. 이 최소의 경로가 "최적"의 경로라고 할 수 있는데 일반적인 해결 알고리즘이 존재하지 않습니다. 이 때, "최근접 이웃 방법"을 통하여 최소값은 아니더라도 근사값을 구할 수 있습니다. 본 코드는 최근접 이웃 방법 알고리즘을 이용하여 모든 정점에서 최소값의 근사값을 구한 후 그 중 최소값을 출력합니다. 위의 그림의 최소경로는 2->3->1->4->2이며 그값은 75입니다. 필요한 변수 - 정점의 개수를 나타내는 n - 정점사이의 경로값을 나타내는 .. 2017. 11. 10. 다익스트라(Dijkstra) 알고리즘 자바로 구현하기 - Dijkstra 알고리즘이란? 그래프의 출발점으로부터 거리가 최소로 알려진 정점들의 집합 S를 유지하고 가장 최소 경로를 가지는 나머지 점을 차례로 집합 S의 포함시켜 가면서 출발점에서 마지막 점까지의 최소 경로를 구하는 알고리즘입니다. 위의 출발점 1에서 마지막 점 5까지 가는 최소 경로는 50입니다. 필요한 변수 - 각 정점들을 담은 집합 v - 최소 경로를 가지는 정점의 집합 s - v에서 s집합의 정점을 뺀 정점을 가지는 집합 v_s - 각 정점까지 경로를 나타내는 집합 d - 각 정점이 갈 수 있는 경로를 저장한 집합 c (각 정점이 도달할 수 없는 경로는 적당히 큰 수로 대체합니다.) 핵심 v_s의 정점 중의 최소 거리를 가지는 정점 을 집합 s의 포함시키고 경로 집합 d의 경로 값을 갱신.. 2017. 11. 7. 이전 1 2 다음 반응형
