Graph & Tree

그래프 정의 - 그래프는 어느 노드와 어느 노드를 연결하는 간선이 있는 자료구조.

 

그래프 실생활 예 - 지도, 내비게이션, 지하철 지도

 

그래프 종류는 간선의 방향, 싸이클 유무에 따라서 나뉠수 있다.

 

간선 방향에 따른 그래프 종류:

무방향 그래프, 방향 그래프, 양방향 그래프 (사실상 무방향 그래프 = 양방향 그래프)

 

싸이클 유무에 따른 그래프 종류:

순환 그래프, 비순환 그래프

 

방향과 싸이클이 합해지면 다음과 같은 그래프가 나올수 있다.

방향성 비순환 그래프(DAG, Directed Acyclic Graph)

DAG의 실생활 예 - VCS(Version Control System), Cryptocurrency

 

------------------------------------------------------------------------------------

두가지 개념의 트리가 존자한다.

 

수학적 개념으로서 트리

트리 정의 - 순환성이 없는 무방향 그래프. 

 

트리 용어와 특징 정리 - 어떤 노드든지 root가 될수 있다. 가장 바깥쪽 노드는 리프 노드(간선이 하나인 노드)이다. 한 노드에서 다른 노드로 가는 경로는 반드시 존재하며 유일하다. 노드 개수 = 간선 개수 + 1

 

전산학에서 등장하는 자료구조 트리

트리 정의 - 부모 -> 자식 관계가 있는 방향 그래프. 루트는 하나이다.

 

 

------------------------------------------------------------------------------------

코드로 그래프를 나타내는 방법은 두가지가 있다.

 

1. 인접 행렬

 

2. 인접 리스트

인접 리스트는 python에서 list로 표현한다.

 

 

인접행렬 vs. 인접리스트

속도

- 인접행렬이 더 빠르다.

 

메모리 공간

- 인접 리스트는 공간을 덜 차지 한다.

 

 

그래프에서 간선 개수가 많은 그래프를 밀집(Dense) 그래프라고 한다.

간선 개수가 많지 않은 그래프는 희소(Sparse) 그래프라고 한다.

 

인접행렬은 밀집 그래프를 사용해야하고,

인접리스트는 희소 그래프를 사용해야한다.

 

보통은 두개중 아무거나 써도 된다.

근데 보통은 메모리보다는 시간이 더 중요한 경우가 있기에 인접행렬을 사용한다.

 

시간 복잡도

인접행렬 O(v^2)

인접리스트 O(V + E) = O(max(V, E))

 

------------------------------------------------------------------------------------

 

그래프 탐색 알고리즘에는 두가지가 있다.

1. DFS(Depth First Search)

 

2. BFS(Breadth First Search)

시작 노드에서 한개의 간선 거리로만 떨어져 있는 노드들을 보고, 그 다음에느 2개의 간선이 떨어져 있는 노드들을 본는 식으로 각 노드들을 access를 한다.

 

큐를 이용한 방법은 다음과 같다.

0 에 연결된 1, 2를 que에 넣는다.

1을 popleft하고, 1과 연결된 3, 4를 넣는다.

2를 popleft하고, 2와 연결된 5, 6을 넣는다.

이런식으로 니머지 노드들을 access한다.

 

DFS vs BFS

차이점:

속도와 코드 간결성

DFS가 코드가 더 간결하다. 재귀함수로 구현이 되기에 그렇다.

BFS가 코드가 더 길다. 

그렇기에 DFS를 쓰는 경우가 더 많다. 그러나 재귀함수는 오버헤드로 인해서 파이썬에서는 느려지는 단점이 있다.

 

최단거리 파악

BFS가 최단거리를 파악하는데 있어서 더 유리하다.