[Algorithm] 그래프(Prim, Kruscal)

그래프의 표현

• 정점 중심 - 인접 행렬, 인접 리스트 : Prim
• 간선 중심 - 간선 리스트 : Kruscal

Kruscal

1. 간선을 비용기준 오름차순 정렬
2. 비용이 가장 작은 간선(두 서로소 집합) 선택하여 신장 트리 처리(union처리)
3. union의 성공을 사이클링의 여부로 볼 수 있다

 

정점이 N인 무향 그래프에서 최대로 가질 수 있는 간선의 개수 : N*(N-1)/2