최소 신장(spannig) 트리

트리 구조

• 여기서의 트리구조는 부모 자식형태의 트리구조를 의미하는 것이 아니라
  싸이클이 발생하지 않는 그래프 구조를 의미한다

무방향 그래프의 스패닝 트리

• 원래 그래프의 정점 전부와 간선의 부분으로 이루어진 부분 그래프이다
• 따라서 하나의 그래프에 여러개의 스패닝 트리가 나올 수 있다

가중치 그래프의 스패닝 트리

• 가중치 그래프의 스패닝 트리중 가중치의 합이 가장 작은 트리를 찾는 문제를 최소 신장 트리(Minimum Sapnning Tree) 문제라고 한다
• 즉, 그래프의 연결성을 그대로 유지하는 가장 '저렴한'그래프를 찾는 문제이다

최소 신장(spannig)트리 문제

• 이를 푸는 대표적인 알고리즘으로 크루스칼의 알고리즘, 프림의 알고리즘 두개가 존재