반응형 알고리즘91 최소 비용 신장 트리 - 프림(Prim) 알고리즘 프림(Prim) 알고리즘 프림 알고리즘이란? - 최소 비용 신장 트리(MST)를 찾는 알고리즘 - 시작 정점에서 출발하여 신장 트리를 확장하는 알고리즘 - 시간 복잡도 : 인접 행렬 사용 시 O($V^2$) 우선 순위 큐, 인접리스트 사용 시 O(ElogV) - 간선의 숫자가 노드의 숫자보다 적은 경우 크루스칼을, 많은 경우 프림을 사용하면 좋다. 프림 알고리즘 실행 과정 - 1. 시작 정점을 선택한다. - 2. 해당 정점과 연결 된 정점 중 선택되지 않은 간선들을 우선순위 큐에 넣는다. - 3. 우선순위 큐에서 값이 제일 작은 간선을 뽑아 연결한다. - 4. 2~3번 과정을 반복한다. - 초기 상태(1을 시작 점을 설정) - 1과 연결된 간선 중 가장 작은 값인 2를 선택하고, 1과 2를 연결한다. -.. 2020. 11. 23. 최소 비용 신장 트리 - 크루스칼(Kruskal) 알고리즘. 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘이란? - 최소 비용 신장 트리(MST)를 찾는 알고리즘 * MST란? Spanning Tree(신장) 중 가중치의 합이 가장 작은 것. Spanning Tree는 모든 노드가 최소의 간선으로 연결된 그래프이다. (노드 N일 때 N-1개의 간선으로 구성된다.) - 탐욕법(Greedy)을 기반으로 간선을 추가해 가면서 MST를 찾는 것이다. - 유니온 파인드 사용 시 시간 복잡도는 O(ElogE)이다. (정렬 시 O(ElogE), E는 간선의 개수) 크루스칼 알고리즘 실행 과정 - 1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다. - 2. 정렬된 간선들을 순서대로 살펴보면서 사이클이 만들어지지 않는 다면 간선을 선택한다. (사이클이 형성되는지는.. 2020. 11. 23. 최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드-워셜 알고리즘 플로이드-워셜 알고리즘 이란? - 모든 정점 사이의 최단 경로, 최단 거리를 구하는 알고리즘 - 다익스트라는 한 정점에서 다른 정점까지의 최단거리이지만, 플로이드-워셜은 모든 정점들 사이의 최단 거리를 구하는 것이다. - 구현이 간단하다. - 구현을 위하여 행렬을 사용한다. - N개의 정점이 존재할 때 O($N^3$)의 시간복잡도를 가진다. 플로이드-워셜 알고리즘 실행 과정 - 1. 행렬의 초기값을 그래프의 인접 행렬과 같은 값으로 설정한다. - 2. 정점i 에서 정점j까지의 최단 경로를 결정할 때 거치는 중간값을 모두 탐색하여 최단 경로를 찾는다. - 3. 모든 정점을 탐색하면 종료한다. - Dist[i][j]를 i에서 j까지 최단 경로라 하면, Dist[i][j] = min(D.. 2020. 11. 23. 최단 거리 알고리즘 - 벨만-포드(Bellman-Ford) 알고리즘 벨만-포드(Bellman-Ford) 알고리즘 벨만-포드 알고리즘이란? - 모든 정점으로 가는 최단 거리를 찾는 알고리즘. - 하나의 정점에서 출발하여 모든 정점으로 가는 최단 거리를 알 수 있다. - 음수의 가중치가 있는 경우에도 최단 경로를 찾을 수 있다. - 음의 사이클이 발생한 경우를 판별할 수 있다. - 최단 경로는 각 정점을 한 번씩만 지나기 떄문에, 최단 경로의 간선 개수는 V-1개 이다. (같은 정점을 지날 때 거리가 줄어든다면, 음의 사이클이 발생한 경우이다.) - 출발 정점에서 1개 ~ V-1개의 간선을 지나서 도착하는 경우를 모두 살펴보고, 그 중 최소 값을 찾아내는 방법이다. - 시간 복잡도는 O(VE)이다. (V은 정점의 개수, E은 간선의 개수) 벨만-포드 알고리즘 실행 과정 - .. 2020. 11. 23. 이전 1 ··· 15 16 17 18 19 20 21 ··· 23 다음 반응형
