최소 스패닝 트리 구현을 명확히하는 데 도움을 줄 수 있습니까?

Question

현재 며칠 내에 예정된 데이터 구조 프로젝트에서 작업 중이며 지침을 이해하지 못합니다. 우리는 kruskal의 알고리즘을 통해 최소 스패닝 트리를 만들지 만 ArrayBasedList, 힙, 위쪽 트리 및 인접 목록을 사용하여 구현해야합니다. 1. 이러한 것들은 나에게 매우 혼란 스럽습니다. 힙과 위쪽의 나무가 다른 순서로 입력 된 것들을 배열 기반의 목록으로 만들겠습니까? 또는 그들 자신의 수업이 필요합니까? 2. 인접 목록이란 무엇입니까? 내 힙, 내 인접 목록 및 내 mst의 문자열 버전을 반환해야합니다. 나는 매우 긴장/혼란스럽고, 어떤 도움을 시작하는 방법을 이해하는 것은 대단히 감사합니다.

프로젝트는 기본적으로 섬 (꼭지점) 사이의 최저 비용 브리지 (에지)의 최소 스패닝 트리를 찾아 가중 그래프로 표시합니다.

Answer 1

먼저 이러한 데이터 구조의 목적을 구분해야합니다. 예를 들어 adjacency list을 사용하여 그래프 정보를 저장합니다. heap은 어디에 사용하나요? 가장자리를 순서대로 처리합니다. 그런 다음 다양한 데이터 구조로 수행 할 수있는 다양한 변형을 찾아보십시오. 데이터 구조는 정보를 다르게 처리하므로 서로 다른 최종 시간 복잡성을 가질 수 있습니다. 조각을 이해하면 그 내용이 어떻게 어울리는지를보고 알고리즘을 구현하십시오.

단계별 데모는과 상담하십시오.