Developer Cafe

신장 트리 n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어져 사이클이 없는 단순 연결 그래프를 신장 트리라고 한다. 깊이 우선 탐색을 이용하여 생성된 깊이 우선 신장 트리와 너비 우선 탐색을 이용하여 생성된 너비 우선 신장 트리가 있다. 최소 비용 신장 트리 무방향 가중치 그래프에서 가중치의 합이 쵯소인 신장 트리를 최소 비용 신장 트리라고 한다. 최소 비용 신장 트리를 만들기 위해 Kruskal이 만든 알고리즘과 Prime이 만든 알고리즘을 사용한다. Kruskal Kruskal 알고리즘은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 Kruskal 알고리즘1 과 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 Kruskal 알..