목록Kruskal 알고리즘 (2)

수학과의 좌충우돌 프로그래밍

[Algorithm] Kruskal 알고리즘

Kruskal 알고리즘이란? Kruskal 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리 Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래.. ssungkang.tistory.com 이 알고리즘은 MST 를 찾기 위해서 greedy 하게 접근합니다. greedy 하게 접근한다는 말은 현재 순간에 최적의 선택을 한다는 의미인데 최소 비용으..
알고리즘/이론 2019. 11. 5. 21:31
[Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리

Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. Spanning Tree 의 특징 Spanning Tree 는 이름에서도 알 수 있듯이 트리 중 하나이기 때문에 트리의 특징은 모두 포함합니다. 하나의 그래프에는 여러 Spanning Tree 를 가질 수 있습니다. 모든 정점을 포함하고 사이클은 생기면 안되기 때문에 N 개의 노드에 대해서 정확하게 N-1 개의 엣지를 가지게 됩니다. MST 란? MST 란 Spanning Tree의 한 종류로서 사용되는 간선의 가중치 합이 최소인 트리를 말합니다. 이 때 ..
알고리즘/이론 2019. 10. 4. 20:34
Prev 1 Next

티스토리툴바