0과1

1. 문제정의 최소 신장 트리 ( Minimum Spanning Tree )란? 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다. BFS , DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다. MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다. 2. 문제 설계 Prim's 알고리즘Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후,그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다. 3. 구현 #include #include #define V 9 //다음에 수행할 정점을..

1. 문제정의 최소 신장 트리 ( Minimum Spanning Tree )란? 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다. BFS , DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다. MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다. 2. 문제 설계 Kruskal's 알고리즘Kruskal's 알고리즘은 두 개의 트리를 연결하는 모든 간선 중 가장 작은 간선( u , v )를 찾아 MST의 부분집합에 추가합니다. Kruskal's 알고리즘은 안전 간선을 연결할 때 Union - Find 자료구조를 이용합니다. 3. 구현 include #include..