[WEEK03] 그래프와 트리 (+인접행렬 / 인접리스트 / 이진트리)

1. 그래프

특징

- 노드와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조

- '서로 다른 개체 혹은 객체가 연결되어 있음' 혹은 '여러 개의 도시가 연결되어 있음' 내용이 나오면 그래프 알고리즘을 일단 생각

 

그래프와 트리의 차이

용어의 정리

1) 정점 (Vertex / Node)

: 각각의 노드를 의미

 

2) 간선 (Edge / Link)

: 그래프에서 각 정점들을 연결하는 선

: 화살표 표시 혹은 그냥 직선

 

3) 가중치 (Weight)

: 간선 위에 표시된 숫자

: 비용을 표현하는 것 등에 쓰임

 

4) Directed Graph / Undirected Graph

: 방향성 혹은 무방향성 그래프

 

5) Adjacency

: 방향성 있는 그래프에서 간선으로 연결된 인접 정점

 

6) Degree

out-degree: 해당 정점에서 나가는 간선

in-degree : 해당 정점으로 들어오는 간선

 

7) Cycle

: 그래프가 path를 따라 동일한 정점으로 돌아올 수 있는 경우

 

8) Acyclic Graph

: 그래프에 사이클이 없는 경우를 의미

 

2. 인접행렬과 인접리스트

인접행렬

- 2차원 배열로 그래프의 연결관계를 표현

- 간선정보를 저장하기 위해 메모리 공간 O(V^2)가 필요 ( V : 노드의 개수 / E : 간선의 개수)

- 노드 A에서 B로 이어진 간선의 비용을 알기위해서 O(1)가 필요

 

인접행렬

인접리스트

- 간선의 정보를 저장하기 위해서 메모리공간 O(E) 필요

- 특정한 노드 A에서 B로 이어진 간선의 비용을 알기위해서 O(V)만큼의 시간이 필요

 

차이점

인접행렬

- 장점 : 특정한 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠름

- 단점 : 메모리가 불필요하게 낭비

 

인접리스트

- 장점 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용

- 단점 : 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림

 

활용예시

- 최단경로 문제 출제되었을 때)

- 노드의 개수가 적으면 : 플로이드 워셜 사용

- 노드와 간선의 개수가 많으면 : 우선순위 큐를 이용하는 다익스트라 알고리즘 사용

 

 

3. 트리

그래프 자료구조 중에서 트리구조는 다양한 알고리즘에서 사용됨

 

트리의 구조

용어의 정리

1) 루트 

: 트리의 가장 위쪽에 있는 노드

 

2) 리프

: 가장 아래 쪽에 있는 노드

 

3) 자식

: 어떤 노드와 가지가 연결되었을 때 아래쪽 노드

 

4) 부모

: 어떤 노드와 가지가 연결되었을 때 위쪽 노드

 

5) 레벨

: 루트에서 얼마나 멀리 떨어져있는가를 나타냄

 

6) 높이

: 루트에서 가장 멀리있는 리프까지의 거리 (리프 레벨의 최댓값)

 

4. 이진트리와 이진검색트리

이진트리 (Binary Tree)

: 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리

 

이진검색트리 (Binary  Search Tree)

: 왼쪽 서브트리 노드의 키 값은 자신의 노드 키 값보다 작고

  오른쪽 서브트리 노드의 키 값은 자신의 노드 키값보다 큰 트리

 

완전이진트리 (Complete Binary Tree)

: 루트부터 아래쪽 레벨로 노드가 가득차있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진트리

  (마지막 레벨을 제외하고 모든 레벨의 노드가 가득차 있음 / 마지막 레벨에 한해서는 왼쪽부터 채우되 끝까지 채우진 않아도 됨)

 

이진검색트리를 쓰는 이유?

- 구조가 단순하고 이진검색과 비슷한 방식으로 빠르게 검색 가능

- 중위순회의 깊이 우선검색을 통해서 노드 값을 오름차순으로 얻을 수 있음

- 노드를 삽입하기가 쉬움

=> 알고리즘에서 폭 넓게 사용되고 있음

 

 

[출처]

서적 : 이것이 취업을 위한 코딩테스트다 / Do it 자료구조와 함께 배우는 알고리즘 입문

블로그 :https://www.leafcats.com/77