[그래프] 최소 신장 트리 (MST) - 크루스칼, 프림
Directed graph도 MST가 있는지, MST 알고리즘을 Directed graph에는 쓸 수 없는지 궁금했다.
기본적으로, MST를 다룰땐 weighted, undirected graph를 지칭하는 것 같다.
en.wikipedia.org/wiki/Minimum_spanning_tree
Minimum spanning tree - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search data structure, subgraph of a weighted graph A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length. A min
en.wikipedia.org
For directed graphs, the minimum spanning tree problem is called the Arborescence problem and can be solved in quadratic time using the Chu–Liu/Edmonds algorithm.
추가) cs.stackexchange.com/questions/897/does-spanning-tree-make-sense-for-dag
크루스칼 vs 프림
최소 신장 트리 (MST, 크루스칼, 프림 알고리즘)
원래의 그래프의 모든 노드가 연결 되어있으면서 트리의 속성을 만족하는 그래프 조건본래의 그래프의 모든 노드를 포함모든 노드가 서로 연결 되어있다트리의 속성을 만족 (사이클이 존재하
velog.io
문제에서 쟁점이 되는 부분이 간선 (Kruskal) 이냐 노드 (Prim) 냐?
ex) BOJ 1647 → 간선을 처리해야 하므로 Kruskal
그래프 알고리즘 정리 (책 내용이랑 비슷)
velog.io/@wan088/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC
그래프 알고리즘 정리
그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. 그래프를 표현하는 세가지 방법 1. 간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현
velog.io
'<PS> > [기본 알고리즘] (정리 예정)' 카테고리의 다른 글
| [그래프] 최단경로 2 (Bellman-Ford) (0) | 2021.05.18 |
|---|---|
| 알고리즘 종류별 정리 (목차) (0) | 2021.03.26 |
| [DP] Dynamic Programming (0) | 2020.12.22 |
| [탐색] DFS /BFS (0) | 2020.12.15 |
| [그래프] 최단 경로 (다익스트라 / 플로이드-워셜) (0) | 2020.12.06 |