[CE] Tree vs. Graph

Graph vs. Tree

Graph

• node와 node를 연결하는 edge로 구성된 data structure(자료구조).
• object들의 network를 모델링하는데 주로 사용됨.

Deep Learning을 가능하게 한 Back-propagation은
Reverse-mode Auto Differentiation에 기반하는데,
이는 Computation Graph을 통해 수행됨.

---

 

Tree

• Directed Acyclic Graph 에서, graph 내의 모든 node와 path가 존재하는 root node라는 것이 1개 있는 자료구조.
• object들의 hierarchy를 모델링하는데 주로 사용됨.

---

Data Structure

• Data를 표현하고 관리하고 처리하기 위한 구조.
• stack, queue, graph, tree등이 기본적인 data structure로 linked list 등으로 구현됨.

---

Tree vs. Graph

	Tree	Graph
Root node 여부	1개의 Root 존재	해당 개념 없음
Parent node 여부	root를 제외하고 모든 node는 1개의 parent node를 가짐	해당 개념 없음
Cycle 여부	Cycle 존재하지 않는 acyclic graph의 일종	Cycle 가능
Direction 여부	반드시 direction을 가지며, 이는 parent-child 관계를 나타냄	Undirected도 가능

---

Graph 와 Tree의 예

Tree의 예

• Class들의 inherence diagram 등이 Tree임.
• binary tree (각 node 는 최대 2개의 child node를 가짐)등이 자주 나옴.

---

Graph의 예

• 통신 기기 간의 네트워크, 지하철 노선도 등이 대표적인 예임.
• Artificial Neural Netwokr등의 구현에서 사용되는 computational graph 등이 유명.

관련 자료.

• [Graph 소개](https://dsaint31.me/mkdocs_site/ML/ch08/datastructure_graph/)

---

Search Algorithm

Graph나 Tree에서의 search algorithm은 매우 중요함.
다음 URL을 꼭 읽어볼 것.

• Breadth First Search (BFS)
• Depth First Search (DFS)

---

search(탐색) 란?

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.
• Graph, Tree 등의 data structure(자료구조) 안에서 search(탐색) 알고리즘을 적용함.

Graph Search란?

하나의 Node(or vertex, 정점)으로부터 시작하여 차례대로 모든 Node들을 한 번씩 방문하는 Task.

1. 특정 node에서 다른 특정 node로 갈 수 있는지 여부 체크 (주로 BFS를 사용).
2. network나 circuit등에서 연결이 되어 있는지 여부를 확인하는데에도 사용됨.