최소신장트리 - 무방향 가중치 그래프
끊어지거나 포함안되는 노드가 없음
크루스칼
유니온 - 파인드를 통해서 서로소 집합, 부모를 찾아서 하는 연산
크루스칼 - 회차가 일어나지 않게 모든 정점을 연결한다
정점 0,1은 9의 가중치를 가지는 간선으로 연결
프림
최소가중치, 트리에 연결된 간선의 가중치로 가중치를 계속 갱신하면서 정점을 추가
양방향으로 연결되있다
0번 정점과 1번 정점의 간선은 가중치 9
0번 정점과 2번 정점의 간선은 가중치 10으로 연결
다른 정점들도 이런 식으로 연결되었다
코드에서는 정점의 갯수만큼 루프를 돌면서
방문하지 않은 가중치가 가장 작은 정점을 찾아서 방문하고
방문한 정점과 인접한 정점(리스트에 들어있는 정점)의 가중치를 갱신한다
시험에서는 코드x, 임의의 시작정점을 주고 최소신장트리 만들기
솔린 알고리즘
독립적인 트리를 만들어서 각 트리가 연결되지 않은 포레스트 상태에서 가중치가 제일 작은 간선으로
각 트리를 연결한다