크루스칼 썸네일형 리스트형 크루스칼 알고리즘 안녕하세요~ (블로그에 포스팅할때는 도대체 누굴 대상으로 글을 쓰는지 늘 스스로 의문입니다?) 최소신장트리에 대해 써볼까 합니다. 처음에 최소신장트리라는 용어를 접했을때 해석할 수 없는 '신장'의 의미 때문에 용어와 의미를 좀처럼 연결시키지 못했던 기억이납니다. 신장(spanning)이라는 용어는 "걸치다" 라는 의미로 번역되는데, 쉽게 말해 그래프 상에서 트리가 모든노드에 걸쳐 연결되어 있다는 의미로 사용됩니다. 여기서 모든 노드에 걸쳐있다는 의미는 path를 만들어 순회한다는 개념이 아닌 모든 노드가 연결되어있다는 의미 입니다. 좀더 형식적으로 정의해보면 신장트리(spanning tree)는 그래프 G=(V,E) 에서 |V| - 1 개의 edge를 제외한 모든 edge를 제거하여 트리가 되도록 만든 .. 더보기 이전 1 다음