이것이 코딩 테스트다 :: 그래프 이론

크루스칼 알고리즘 -> 그리디

위상 정렬 알고리즘 -> 큐, 스택 자료구조

 

노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조

 

노드의 개수 V

간선의 개수 E 

 

플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식

 

! 노드의 개수가 적은 경우 플로이드 워셜 알고리즘 이용

! 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘 이용

 

[서로소 집합 자료구조]

union-find 자료구조 

 

[신장 트리(Spanning Tree)]

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건

 

[크루스칼 알고리즘]

최소한의 비용으로 신장 트리를 찾는 경우

최소 신장 트리 알고리즘 

 

모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함