[알고리즘]그래프(최소신장트리, 다익스트라)

최소 신장 트리란

그래프의 속성을 가지고 있으며 간선에 가중치를 추가 한 그래프의 하위 개념인 트리

최소한의 비용으로 모든 도시를 연결하는 도로를 설계하는 문제를 풀기 적합한 알고리즘

간선의 가중치를 기준으로 사이클을 제거하여 필요한 정보만 가지는 방식

가중치를 가진 트리 / B를 시작으로가중치에 따라 사이클을 제거하고 빠른 길을 찾은 트리

최소 신장 트리 알고리즘

가장 작은 가중치를 가지는 트리를 만드는 알고리즘

- 프림(Prim) 알고리즘 : 정점에 연결 된 간선의 가중치 중 가장 작은 가중치의 간선을 연결해 나가는 방식

- 크루스칼(kruskal) 알고리즘 : 모든 간선의 가중치를 조사하고 정렬 후 순서대로 연결해 나가는 방식

-> 최소 신장 트리에서 발생하는 사이클은 깊이 우선 탐색 방법으로 해결할 수 있지만 성능 저하

-> 분리 집합을 이용하여 해당하는 연결 되지 않은 정점을 순서대로 연결해 나가는 방식 선호

다익스트라란

최단 경로를 찾는 알고리즘

출발지부터 목적지까지의 최단 경로를 찾기 위한 알고리즘

출발지부터 목적지까지가는 다양한 경로들의 가중치를 누적하여 최소의 노력으로 목적지까지 가는 방식

소스는 깃허브에 올렸습니다.