MST1 스패닝 트리(Spanning Tree), 최소비용신장트리(MST), 프림(Prim) 알고리즘 MST와 Prim 알고리즘에 대해 공부해 보자. 목차는 다음과 같다. Spanning Tree란? MST란? Prim알고리즘 Prim알고리즘 실전 문제 그럼 이제 Spanning Tree에 대해 알아보자. Spanning Tree란? 모든 정점(노드)을 포함하면서 간선의 개수가 최소인 트리를 말한다. 특징은 다음과 같다. 앞서 말한 듯 모든 정점을 포함하면서 간선의 개수가 최소다. 사이클이 없는 그래프다.(사이클이 없는 그래프를 트리라고 말한다.) 그럼 위 2가지 특징을 통해 알 수 있는 사실이 있다. Spanning Tree는 모든 정점을 포함하면서 간선의 개수가 최소이려면 간선의 개수는 정점 - 1이 될 수밖에 없다. 이와 관련되어 좀 더 자세히 알아보자. 위와 같이 그래프가 존재할 때 Spannin.. 2024. 3. 19. 이전 1 다음
