본문 바로가기
반응형

분류 전체보기110

최소 비용 신장 트리 - 크루스칼(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.
최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra) 다익스트라(Dijkstra) 다익스트라 알고리즘이란? - 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다. - 가중치가 양수인 경우에만 사용할 수 있다. - 가중치 중 음수가 존재하지 않기 때문에 그래프에 있는 모든 간선을 단 한 번만 처리한다. - 우선순위큐를 이용하여 효율적으로 구현할 수 있다. 다익스트라 실행 과정 - 1. 모든 정점의 거리값을 무한으로 설정한다.(시작점의 거리값은 0) - 2. 시작 노드와 인접한 노드들의 거리값을 설정한다. 시작 노드의 거리값 + 인접한 노드까지의 가중치 < 인접한 노드의 거리값 인 경우 인접한 노드의 거리값을 갱신한다. 인접한 노드의 거리값이 갱신된 경우 해당 노드를 우선순위큐에 넣는다. - 3. 우선순위 큐의 루트 노드를 선택하고, 해당 노드가.. 2020. 7. 16.
반응형

티스토리툴바