크루스칼

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

날짜 : 2021 년 11 월 6 일 시청 강의 : 프림 알고리즘 (1), 프림 알고리즘 (2) 오늘 시청한 강의는 프림 알고리즘이다. 내가 뭘들은건가싶다 주르륵.. 크루스칼은 이해가 좀 됬는데 역시 옛날부터 포기한 프림 알고리즘은 차원이 달랐다.. 일단 개념만 이해하고 코드는 나중에 이해하기로 결심했다. 크루스칼 vs 프림 알고리즘 1. 크루스칼 알고리즘 : 간선 정보를 정렬 -> 가장 가중치가 낮은 간선부터 사이클이 생기지 않도록 연결 2. 프림 알고리즘 : 시작 정점을 선택 -> 정점의 인접 간선 중 가중치가 최소인 간선을 연결 프림 알고리즘 https://www.cs.usfca.edu/~galles/visualization/Prim.html Prim MST Visualzation www.cs.us..

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

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