Data Structure - Graph, Tree

graph

• Graph는 Vertex와 Edge의 쌍이다.
  • V는 vertex(혹은 node, 정점)의 집합(set)이고 E는 edge(간선)의 집합이다.
  • vertex는 독립된 개체로 동그라미로 표현하고 edge는 두 vertex를 잇는 개체로 선이나 화살표가 있는 선으로 표현한다.

 

1. Directed graph

• 방향성이 있는 간선을 가지는 그래프
• 화살표가 있는 선을 사용한다.
• 일반적으로, 각 vertex는 숫자나 이름(알파벳)으로 구분한다.
  • V = {1,2,3,4,5,6}

• edge는 두 개의 (출발 vertex, 도착 vertex)로 나타낸다.
  •   E = {(1,2,)(2,2),(2,4),(4,5),(5,4)}
• 2 개의 vertex에 대해 최대 2개의 간선이 존재할 수 있다.
  • 즉, (4,5)는 (5,4) 서로 다른 edge이다.
• tree도 directed graph라서 사실 방향을 나타내 주어야 하지만 트리구조는 위에서 아래로만 작동하니까 생략해준다.
• self edge 로 자기 자신을 가리키는 것도 있다.

 

 

2. Undirected graph

• 무방향성 간선을 가지를 그래프
• 방향이 없으므로 직선을 사용한다.
• edge (4,5) = edge(5,4)

 

Terms

Adjacency 인접

 

(u,v)라는 edge가 있으면 vertex v와 vertex u가 '인접하다' 고 할 수 있다.

• undirected graph에서는 인접괍계는 동일하다. 즉, u가 v에 인접하면 v도 u에 인접하다.
• directed graph에서 인접관계는 동일하지 않다.

 

directed graph에서 '인접하다' 라는 것은

도착 vertex를 기준으로 얘기한다.

 

왼쪽 그림을 예시로

vertex2 (도착)는 vertex1에 인접하지만 그 반대는 성립하지 않는다.

:즉, vertex1로부터 vertex 2로 갈 수 있다.  

 

 

 

Degree 차수

• Directed graph
  • 진출 차수 (out-degree) : vertex를 나가는 edge의 수
    • 위 예시에서 vertex2의 진출 차수는 3이다.
  • 진입 차수(in-degree) : vertex로 들어오는 edge의 수
    • 위 예시에서 vertex2의 진입 차수는 2이다.
  • 일반적으로 말하면 차수는 진출 차수와 진입 차수를 합친 것이다.
    • degree = out-degree + in-degree

 

• Undirected graph

진입 차수와 진출 차수는 정의할 수 없고 차수만 정의할 수 있다.

vertex2의 차수는 3이다.

 

 

 

 

 

 

 

cyclic

: 적어도 하나의 싸이클을 가진 그래프

acyclic

: 싸이클이 하나도 없는 그래프

 

 

 

그래프를 표현하는 2가지 방법

1. adjacency Matrix : 2차원 배열에 표현하는 방법

• 그래프를 표에 표현
• 서로 연결된 노드는 1, 연결이 없으면 0을 넣어서 표현

 

2. adjacency List : 배열에 노드들을 나열하고 인접한 노드들을 linked list 로 표현하는 방법

• 배열에 노드들을 넣고
• 연결이 있는 노드들을 linked list로 순서 상관 없이 나열한다.
• 엣지의 갯수를 m 이라고 할 때 총 노드의 갯수는 2m개 

 

 

tree 

 

부모-자식 관계이므로 계층, 그룹이 있음

트리의 노드 중에는 부모를 아는 경우, 자식만 아는 경우, 데이터가 섞여 있는 경우 등 많음

 

binary tree 이진 트리 ( 유용)

• 노드가 최대 2개까지만 붙는 트리

 

binary search tree (BST) 이진 탐색 트리

• 노드가 최대 2개 붙으면서 그 안의 데이터가 
• 왼쪽노드와 그 이하 child node들은 현재 노드 보다 작아야 하고
• 오른쪽 노드와 그 이하 child node들은 현재 노드보다 크거나 같아야 한다.

 

< 발란스>

balanced : red-black tree, AVL tree

unbalanced : 너무 한쪽으로만 치우진 트리

 

complete binary tree 완전 이진 트리

: 모든 노드들이 왼쪽부터 채워져 있으면 됨

 

full binary tree 포화 이진 트리

하나의 child 노드를 가진 노드가 없다

즉. 노드가 child가 없거나 2개 이거나

 

perfect binary tree

양쪽으로 노드들이 레벨도 같고 모든 노드가 2개의 자식을 가지는 것

완벽한 피라미드 구조

레벨의 갯수를 n이라고 할 때 2n승 -1 개의 노드를 가진다.

 

f,g 처럼 자식 노드가 없는 노드는 leaf 라고 한다.

아마도 위 트리는 최대 2개의 노드를 가지는데 왼쪽부터 채워져 있으니까 complete binary tree 이면서

자식이 하나인 노드가 없기 때문에 full binary tree 도 될 것 같다.