kruskal

패스트캠퍼스 챌린지 5일차

날짜 : 2021 년 11 월 5 일 시청 강의 : 최소 신장 트리의 이해와 크루스칼 알고리즘 (1) ~ (4) 그래프 탐색 : 크루스칼과 프림 알고리즘은 최소 신장 트리를 활용하는 문제이다. 이중에서, 오늘은 크루스칼 알고리즘에 대해 배웠다. 신장 트리 (Spanning Tree) 전체 노드가 연결되어 있다. 사이클이 존재하지 않는다. 위 그래프에서, 그래프 G 는 사이클이 존재한다. 스패닝 트리는, 모든 노드가 연결되어있으면서 사이클이 존재하지 않는 그래프다 최소 신장 트리 가중치가 존재하는 신장 트리 중, 간선의 합(weight)이 가장 작은 트리 만약, 앞의 신장 트리가 다음과 같은 가중치를 가지고 있다고 가정해보자. 그렇다면, 최소 신장 트리는 가중치가 가장 작은 트리로 첫번째 스패닝 트리가 최..