패스트캠퍼스 챌린지 16일차

프림 알고리즘 (Prim's Algorithm)

 - 시작 정점을 선택한 후 , 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는방식, 

 - 최소 신장 트리를 확장해가는 방식

 

구현

1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서, => 최소 Heap , PriorityQueue 사용
   - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 넘어간다 (사이클 방지)
   - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 최소 신장 트리에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

 

• HashMap에 특정 키 존재 여부 확인 메서드

   - containsKey("키")

• 찾는 키에 대한 값이 없을 떄, 디폴트 값 반환 메서드

   - getOrDefault("키", default 값)

 

 

개선된 프림 알고리즘

 - 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식

 -  가장 키 값이 적은 정점을 추출한 후 해당 정점의 인접한 정점들에 대해 키값과 연결된 가중치 값을 비교하여

    키 값이 작으면 해당 정점 값을 갱신

 - 우선순위큐 구조에서 이미 들어가 있는 데이터의 값 변경 시, 최소값을 가지는 데이터를 루트노드로 올려놓도록

   재구성하는 기능이 필요하다.

 - 다익스트라 알고리즘과 비슷한 방식

 

개선된 프림 알고리즘의 시간 복잡도 : O(ElogV)

 

16일차 인증

 

 

이것 또한 개념 및 코드에 어려움을 느꼇다.. 다시 한번 강의보며 예제를 작성하고 이해하면서 파악할 시간이 필요할듯하다

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]