아래의 그래프에서 프림(Prim)의 최소 신장 트리 알고리즘(PrimMST)이 수행되는 과정을 단계별로 정확히 그리시오. 임의의 시작점으로 점 A가 선택되었다고 가정하고 시작하시오.

소개글

"아래의 그래프에서 프림(Prim)의 최소 신장 트리 알고리즘(PrimMST)이 수행되는 과정을 단계별로 정확히 그리시오. 임의의 시작점으로 점 A가 선택되었다고 가정하고 시작하시오."에 대한 내용입니다.

목차

없음

본문내용

1. 최소신장 트리 정의
1.1 주어진 가중치 그래프에서 사이클이 없이 모든 점을 연결한 트리 중 가중치 합이 최소인 트리
1.2 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결
1.3 그래프의 점의 수가 n이면 신장 트리에는 정확히 (n-1)개의 선분이 존재
2. 프림의 최소 신장 트리 알고리즘
최소 신장 트리를 찾는 대표적인 그리디 알고리즘
2.1 크러스컬(Kruskal)과 프림(Prim)알고리즘
2.2 알고리즘의 입력은 1개의 연결요소 (connected component)로 된 가중치 그래프
2.3 프림 알고리즘은 집합 A의 간선이 항상 하나의 트리를 이룸
2.4 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, (n-1)개의 선분을 하나씩 추가시켜 트리를 작성
2.5 추가되는 선분 ⇨현재까지 만들어진 트리에 연결시킬 때 ‘욕심을 내어서’ 항상 최소의 가중치로 연결되는 선분

참고 자료

없음