9-11주차- heap, graphs (힙과 그래프)

수강기간: 2020.09-2020.12

출처: 고려대학교 정연돈교수님 자료구조 수업

 

 

힙은 binary 트리이지만 bst와는 다르게 노드의 크기를 기준으로 좌우로 크기를 나눈것이 아닌 매 루트의 크기가 전체 트리에서 가장 작거나 가장 큰 tree를 말한다.

 

그림으로 차이를 보면 다음과 같다.

MIN heap은 루트가 가장 작은경우

MAX heap은 루트가 가장 큰 경우를 말한다.

 

힙의 장점은 가장 크거나 작은 값을 바로 찾을 수 있다.

힙은 array를 통해서도 비교적 효과적으로 구성할 수 있다.

complete tree이므로 2n+1이 왼쪽자식 2n+2가 오른쪽 자식 노드가 된다.

 

 

힙의경우 insert, delete의 과정에서

다시 힙으로 만드는 reheap의 과정이 필요하다.

 

힙에 insert하는경우의 reheap up 과정은 다음과 같다.

 

마지막 자리에 insert한 후 부모노드와 비교하며 올라간다.

 

 

 

 

 

 

 

 

 

 

 

 

recursive한 방법으로 구현한 코드는 아래와 같다.

 

 

힙의 첫번째 노드를 delete  하는경우의 reheap down 과정은 다음과 같다.

 

빈 자리에 left노드 또는 right노드를 넣고 reheap down과정을 반복한다.

 

 

그래프는 tree보다 일반적인 형태로 노드와 엣지의 집합이다.

방향이 존재할수도 없을수도 있으며 엣지의 크기도 존재할 수 있다.

연결성을 기준으로 강하게연결, 약하게연결, 떨어진 그래프 등으로 나타낸다.

그래프의 연결을 matrix로 표현하기도 하는데 이를 adjacency matrix라고 한다.

연결된 부분(갈 수 있는 방향)을 1로 표시한다.

 

그래프의 깊이우선탐색 순서는 다음과 같다.

 

 

Spanning트리는 각 엣지간에 단일연결로 된 트리를 말한다.

그중에서도 MST(minimum spanning tree는 cost가 가장 낮은 spanning tree를 말한다)

 

이를 만드는 방식으로는 크루스칼의 방법

프림의 방법

솔린의 방법등이 있다.

세 방법 모두 greedy 한 방식으로(각 회차마다 단기적으로 최선의 방식을 취하여 최종적으로 합함)구한다,

 

그중 프림의 알고리즘은 다음과 같다.

1. 한 노드를 선택하고 완성집합에 삽입한다.

2. 선택된 노드에 연결된 엣지들을 엣지 리스트에 삽입한다.

3. 엣지 리스트에서 최소거리를 가지고 해당 엣지에 연결된 인접 노드들이 완성집합에 들어있다면, continue

들어있지 않다면, 해당 엣지를 선택 후 해당 엣지 정보를 '최소 신장 트리'에 삽입한다.

4. 추출한 엣지를 엣지리스트에서 제거한다.

5. 더이상 진행을 할 수 없을때까지 반복한다.