CodeAngie

1. 신장 트리 (Spanning Tree)신장 트리는 모든 노드끼리 연결되어 있는 (모든 노드 간에 경로가 존재하는) 연결 그래프가 주어졌을 때, 모든 노드가 연결되지만 사이클이 존재하지 않는 부분 그래프를 의미한다.그래프의 최소 연결 부분 그래프라고 할 수 있다.여기서 최소 연결이란, 간선의 수가 최소가 되는 부분 그래프를 의미한다.n개의 노드가 있을 때 간선의 수는 n-1이 된다.2. 최소 신장 트리최소 신장 트리는 연결 그래프가 주어졌을 때, 가능한 신장 트리 중 가중치 합이 가장 작은 트리이다.2.1. 최소 신장 트리의 특징간선의 가중치 합이 최소여야 한다.노드가 n 개일 때, 간선은 반드시 n-1 개다. (신장 트리 특징)사이클이 존재하지 않는다. (신장 트리 특징)3. 크루스칼 (Kruska..