MST2 [알고리즘] ep6+) Prim-Jarnik과 Kruskal 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) Prim-Jarnik 알고리즘 구현입력으로 주어지는 그래프를 Prim-Jarnik 알고리즘을 이용하여 최소신장트리(Minimum Spanning Tree, MST)를 생성하는 프로그램을 작성하고, 최소신장트리의 생성 과정과 총무게를 결과로 출력하시오. 입력 그래프의 성질: n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m .. 2024. 7. 26. [알고리즘] ep6) 최소신장트리(MST) ㅁ가중그래프(weighted graph): 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프 무게의 예: 거리, 비용, 시간 등 이 철도 그래프에서는 간선의 무게가 여행거리를 표현한다 신장 부그래프: 그래프 G의 모든 정점들을 포함하는 부그래프신장트리(spanning tree): 모든 정점이 다 이어져 있으면서, 싸이클이 없는 무방향 그래프 (자유 트리인 신장 부그래프)ㅇ최소신장트리(MST, Minimum Spanning Tree): 가중그래프의 총 간선 무게가 최소인 신장트리응용: 통신망, 교통망 [MST 속성 2가지] - MST 알고리즘 정확성 검증에 이용1. 싸이클 속성T를 가중그래프 G의 MST라 하자e를 T에 존재하지 않는 G의 간선으로, C를 T에 추가하여 형성된 싸이클로 가정그.. 2024. 7. 25. 이전 1 다음
