자료구조&알고리즘

합집합을 찾을 때 주로 사용서로소 집합 알고리즘이라고도 함여러 노드 중에서 그룹화를 지을 때 사용하는 알고리즘크루스칼 알고리즘 구현 시 싸이클이 발생하지 않도록 판별할 때 사용하는 등 다양한 알고리즘 문제 적용시 사용이 됨무방향 그래프에서 적용\*문제 상황노드의 연결

MST(Minimun Spanning Tree)구현 시 사용되는 알고리즘크루스탈 알고리즘 간선을 정렬하여 작은 간선부터 추가 해 주는 방식으로 부분적인 트리를 완성하면서 나중에 하나의 트리로 만드는 과정이라면 프림 알고리즘은 하나의 노드를 시작으로 트리를 형성하는 구조

다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘인공위성 GPS 소프트웨어 등에서 많이 사용이 됨특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 찾아줌무방향, 유방향 그래프 두 종류 다 작동을 함\*문제상황4번 노드에서 6번 노드로 가는 최단 경로를 찾아

\*MST(Minimum Spanning Tree)Spanning Tree : 그래프 내의 모든 노드를 포함하는 트리Minimum Spanning Tree: Spanning Tree중에서 사용된 간선들의 가중치 합이 최소인 트리\*크루스칼 알고리즘(Kruskal Alg