# spanningtree
[Algorithm] Kruskal 크루스칼
개요 여러 정점과 간선들로 이루어진 양방향 그래프가 있을때 부분 그래프가 최소한의 간선들로 이루어 졌을때 Spanning Tree, 신장트리라고 한다. 즉 Spanning Tree는 내부에 사이클이 없는 그래프를 의미하는것이다. 사이클이 생기는 순간 불필요한 간선이 하나 더 있는것이니까. 여기에서 모든 간선들의 가중치합이 최소가 될때 최소 신장 트리, Minimum Spanning Tree, MST라고 한다. 이러한 MST는 네트워크 라우팅, 통신망 설계등 실생활에서 자주 사용되는 개념이다. 작동원리 > 1. 최소 가중치의 간선들로만 이루어져야하므로, 가중치에대해 오름차순으로 정렬한다. 사이클이 형성되는순간 최소의 간선갯수(스패닝 트리 조건)에 위배 되므로 사이클이 형성되지 않도록 간선을 선택. 위 두 과정을 동시에 진행하면된다. 이때 2번과정은 DSU알고리즘의 일부인 find, union함수를 가져다가 쓸 것이다. (DSU알고리즘 >> https://velo
백준 1197번. 최소 스패닝트리 (Python)
문제 : https://www.acmicpc.net/problem/1197 풀이 최소 스패닝 트리를 이용해 푸는 문제이다. 크루스칼 알고리즘을 이용했다. 노드가 어떤 노드와 연결되어 있는지 정보를 담을 nodes 배열과, 어떤 노드가 연결되어 있고 가중치가 몇인지 담을 배열 li를 준비한다. 두가지 함수를 준비한다. find함수는 노드a가 연결되어 있는 루트노드를 찾아 리턴한다. union함수는 a와 b의 루트노드가 다를 경우, 연결하여 준다. li배열을 가중치 오름차순으로 정렬해 준다. li배열을 순회하면서 a와 b의 루트노드가 다를경우, 결과값가중치에 v를 더해주고, a와 b를 union 해준다. 마지막으로, 결과값가중치를 출력