Problem solving/Algorithm6 최소 스패닝 트리 알고리즘 (크루스칼, 프림) 최소 스패닝 트리(Minimum Spanning Tree, MST) 그래프의 모든 정점을 사이클이 존재하지 않도록 연결했을 때, 간선의 가중치의 합이 최소인 트리 특징 무방향 그래프 하나의 그래프에서 최소 스패닝 트리는 여러개일 수 있다. 간선의 개수는 N-1개이다 크루스칼(Kruskal) 알고리즘 가중치가 낮은 간선일수록 최소 스패닝 트리에 포함될 가능성이 클 것이다. 이런 점을 이용하여 그래프의 모든 간선을 오름차순으로 정렬 후 사이클이 생기지 않도록 트리에 하나씩 추가해보는 알고리즘이다. 사이클을 확인할 때는 유니온 파인드를 이용한다. 알고리즘 구조 // 1. 모든 간선을 우선순위 큐에 넣어 오름차순으로 정렬 sturct cmp { bool operater()(Edge& e1, Edge& e2) {.. 2023. 7. 21. 최단 경로 알고리즘 (BFS, 다익스트라, 벨만 포드, 플로이드 워셜) 최단 경로 문제를 풀 때, 어떤 알고리즘을 선택해야하는지 정리하기 위한 글이다. BFS 2차원 배열에서 최단 경로를 구해야하는 문제를 볼때마다 BFS를 사용해서 문제를 풀었다. 항상 최단 경로 문제를 풀 때마다 이를 활용해서 문제를 풀다가 정답을 구할 수 없는 경우가 발생했다. 바로, 가중치가 있는 경우이다. 위와 같은 그래프가 있을 때, a에서 b로 가는 최단 거리를 구하려고 한다. BFS방식을 사용한다면 a와 연결된 b, d노드로 가게 될 것이고, b노드를 발견한 즉시 탐색을 종료하게 된다. a → b 경로는 12의 거리가 소요되고, a → d → c → b 경로는 9의 거리가 소요되지만 먼저 방문한 노드가 우선시 되는 것이다. 위의 이유로 일찍 만난 노드가 가장 우선시 되어 종료될 수 있는 경우 가.. 2023. 7. 21. 이전 1 2 다음
