MST
프림 알고리즘 (Prim Algorithm)
👉 크루스칼 알고리즘과 같은 원리로 동작하는 또 다른 스패닝 트리 알고리즘이다. 💡 크루스칼 알고리즘이란? 참고 : https://withseungryu.tistory.com/70?category=753127 크루스칼 알고리즘 (Kruskal Algorithm) 👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 � withseungryu.tistory.com 프림 알고리즘과 크루스칼 알고리즘의 큰 차이는 진행 방식입니다. 크루스칼 알고리즘은 여기저기서 산발적으로 만들어진 트리의 조각들을 합쳐 스피닝 트리를 만드는 방법이고, 프림 알고리즘은 하나의 시작점으..
크루스칼 알고리즘 (Kruskal Algorithm)
👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식으로 동작합니다. 하지만, 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것이 아닌, 사이클이 생기는 간선을 고려해 제외 해줍니다. 👉 동작하는 과정 위 그래프를 보면 가중치가 1인 간선, 2인 간선, 3.. 순서대로 선택해 가고 있습니다. 이때 4번째에서 5번째를 보면 가중치가 3인 간선들이 남아 있는데도 불구하고, 4인 (c,d) 간선이 추가됩니다. 그 이유는 3인 간선들이 추가되면 트리..