MST1 MST (Minimun Spanning Tree, 최소 신장 트리) 그래프와 트리비선형 자료구조 : 객체간의 관계를 관리하며 하나의 자료 뒤에 여러 개의 자료가 존재그래프 : 노드(정점, 위치), 간선(위치간 관계), 가중치(간선에 할당된 비용)로 이루어진 자료구조유향 그래프, 무향 그래프 : 단방향이면 유향, 양방향이면 무향트리 : 사이클 없이 모든 노드가 하나의 연결 요소인 그래프사이클 - 단순 경로(노드가 중복되지 않은 경로)의 시작점과 종점이 동일한 그래프→ 노드의 개수가 n개일 때, 간선의 개수는 n-1개 이다.기본 트리는 루트를 고려하지 않음, 루트를 고려하면 루티드 트리가 된다.신장 트리(Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리→ 최소 연결(간선의 수가 가장 적은 부분 그래프)→ n개의 노드에 n-1개의 간선으로 모두 연결된 그래.. 2024. 6. 26. 이전 1 다음