Leta Learns

Prim 알고리즘 대표적인 최소신장트리 알고리즘 ex) Prim, Kruskal 알고리즘 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법 정점 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리를 확장하는 방법 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치로 연결된 정점을 선택. 해당 정점에서 다시 최소 가중치로 연결된 정점을 선택. => 그리디 알고리즘 Prim 알고리즘 예 임의의 정점을 선택. 연결된 노드 집합에 삽입. 현재 정점에 연결된 간선들을 간선 리스트에 삽입 간선 리스트에서 최소가중치를 가지는 간선 추출 추출한 간선은 간선 리스트에서 삭제 간선 리스트에 더 이상 간선이 없을 때 까지 3,4번 반복 3번 과정에서, if 해당 간선에 연결된 정점이..

Spanning Tree (신장 트리) : 그래프의 최소 연결 부분 그래프. 최소 연결 -> 간선의 수가 최소 n개의 정점을 가지는 그래프의 최소 간선의 수: n-1 n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. => ST 즉, 그래프에서 일부 간선을 선택해서 만든 트리. Spanning Tree의 특징 하나의 그래프에는 여러 개의 신장 트리가 존재 가능. ST는 트리의 특수 형태 => 모든 정점들 연결 => 사이클 포함 x => N개의 정점을 정확히 n-1개의 간선으로 연결 Minimum Spanning Tree (최소 신장 트리) : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 상이할 때 단순히 간선 수를 가장 적게 사용한다고 해서 ..