Kruskal algorithm

[백준(BOJ)] #1197- 최소 스패닝 트리 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 이 문제는 최소 신장 트리의 가중치를 구하는 문제로 크루스칼 알고리즘을 적용하여 풀었습니다. 2022.07.29 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘 [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘 크루스칼(Kruskal) 알고리즘이란? 2022.07.28 - [..

[파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

크루스칼(Kruskal) 알고리즘이란? 2022.07.28 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST) [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST) 신장 트리 신장 트리(Spanning Tree)란 그래프 내의 모든 노드를 포함하면서 사이클(Cycle)이 없는 부분 그래프를 의미합니다. 이때 모든 노드를 포함하면서 사이클이 없다는 조건은 트리의 성립 조건 c4u-rdav.tistory.com 만약 최소 신장 트리의 개념과 크루스칼 알고리즘의 개념을 모르신다면 위의 포스팅한 글을 보고 간단한 개념을 알고 오시는 게 좋을 것 같습니다! 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘이라고 했는데 오늘은 크루스칼 알고리즘을 사용해서 최소..

[파이썬으로 배우는 알고리즘] 최소 신장 트리(MST)

신장 트리 신장 트리(Spanning Tree)란 그래프 내의 모든 노드를 포함하면서 사이클(Cycle)이 없는 부분 그래프를 의미합니다. 이때 모든 노드를 포함하면서 사이클이 없다는 조건은 트리의 성립 조건이기도 하기 때문에 트리라고 불립니다. 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph) [파이썬으로 배우는 자료구조] 그래프(Graph) 그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다. 두 노드가 연결되어 있 c4u-rdav.tistory.com 2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tr..