오늘은 신장 트리에 대하여 알아보겠습니다.

개요

신장 트리는 n개의 정점으로 이루어진 무방향 그래프 g에서

n개의 모든 정점과 n-1개의 간선으로 이루어진 트리입니다.

링크드 리스트

링크드 리스트에서 순회를 하게 되면,

n-1개의 간선을 이동하며 모든 정점을 방문하면서 신장 트리를 만들게 됩니다.

종류

깊이 우선 탐색을 이용하여 생성된 신장 트리는 깊이 우선 신장 트리라고 하며,

너비 우선 탐색을 이용하면 너비 우선 신장 트리라고 불립니다.

사용되는 곳

최종적으로 신장 트리는 최소의 간선을 이용해 모든 정점을 연결한 그래프가 되며,

도로망 건설 및 통신망 설계에서 사용됩니다.

최소 비용 신장 트리

가중치의 합이 최소인 신장 트리를 최소 신장 트리라고하며,

대표적으로 알고리즘은 두개가 있습니다.

• kruskal

• prime

다음 포스트에서 최소 비용 신장 트리에 대하여 이어집니다.