목록최소신장트리 (1)

KKanging

[자료구조] 최소 신장 트리(MST: Minimum Spanning Tree)란

최소신장 트리(MST: Minimum Spanning Tree)란 그래프의 정점이 다 포함되어있는 트리( 신장 트리 (spanning tree)) 가중치 그래프가 주어질 경우 간선들의 비용 합이 최소가 되는 신장 트리 cycle이 발생하면 안됨 그래프란 → 노드(정점 vertex)와 그 노드를 연결하는 간선을(edge) 하나로 모아놓은 자료구조 무방향 그래프: 간선이 방향이 없는 그래프 방향 크래프: 간선의 방향이 있는 그래프 그래프의 표현 방법 인접 행렬 인접 리스트 인접행렬 가중치 그래프란 그래프의 간선에 가중치(weight)를 부여한 것 트리란 → 그래프의 한 종류 → Cycle이 불가능 (그래프에서 사이클(Cycle)이란 어떤 특정 정점에서 출발하여 간선과 정점들을 지 나 다시 처음에 출발했던 특..
cs/자료구조 2023. 8. 6. 03:25
이전 Prev 1 Next 다음