'2024/11/21 글 목록

그래프의 path그래프에는 다양한 path가 있다. 기본적인 path는 vertex에서 서로 다른 vertex로 가는 간선이다. Simple path는 시작과 끝이 같지 않은 모든 vertex와 edge가 한 번씩만 나타나는 path이다. Cycle은 시작 vertex와 끝 vertex가 동일한 simple path를 의미한다.spanning treespanning tree는 ‘신장 트리’라고도 하며 cycle 없이그래프 내의 모든 정점을 포함하는 트리를 의미한다. 때문에 정점이 n개라면 spanning tree는 n-1개의 edge를 가진다.MST vertex를 가장 적은 수의 edge로 연결한 신장 트리를 의미한다.구현방법구현 방법: Kruskal’s MST algorithmvertex의 개수 n가장..