Javascript - Graph, Tree (데이터구조)(4)

내용이 너무 밀려서 큰일이지만, 하루하루 쌓아 조금씩 채워 가야겠다.

 

Graph

Graph는 노드와 연결선으로 구성 되어 있다. 글보단 그림으로 설명이 더 좋을 것 같다.

Node가 있고, Edge로 다음을 연결되어 있는 구조이다.

Graph는 한쪽방향으로만 연결 할 수도 있지만, 양방향으로도 연결할 수 있다.(양방향은 상, 하 관계가 없다)

 

예시를 들면, 현실에서는 주로 지하철 노선을 찾을 때, 많이 사용이 된다. 지금 있는 위치를 A라고 한다면, Node로 지정이 되고 D가 목적 지라면 가는 방법은 분명 다양할 것이다. A - B - D로 갈수도 있고, A-C-D로 갈수 있다. 이와 같이 Graph는 길을 찾을 때, 많이 사용된다.

 

Node가 있으면 다음 노드를 Edge로 연결해서 다음 값을 가르켜 줘야한다. 방향이 있는 구조라면 하기 내용에 있는 Tree와 비슷 하겠지만, 방향이 없다면 graph만의 특징을 갖는다(상, 하 구조 X)

 

 

 

이와 같은 구조가 graph 이며, 이것은 하기 내용에 있는 Tree 구조의 하나이다.

 

코드는 google에 많기 때문에 링크로 참조 : https://medium.com/@ziyoshams/graphs-in-javascript-cc0ed170b156

 

Tree

Tree는 나무 뿌리가 땅속으로 계속 뻗어 나가는 형상이라고 생각하면 된다.

Tree를 구성하는 것은 Node이다. Tree는 node와 node 사이에 parent - child 구조를 가지고 있기 때문에, Graph와 달리 상, 하 구조를 가지고 있다. Tree의 최상위에 있는 Node를 Root라고 부르고 그 밑으로 자식들이 뻗어 나가는 구조이다.

 

from codestates

 

예시를 들면, 현실에서 알파고를 생각하면 된다. 이세돌과 알파고와의 경기를 기억하는가? 2016년 인간과 인공지능간 세기의 바둑 대결이었고 벌써 4년이 지났다. 유일하게 이세돌이 알파고에게 첫승을 안겨줬다.(아직도...)

암튼 바둑으로 예시를 들면, 이세돌이 우상귀화점에 백돌을 두었다고 하면, 알파고 입장에서는 root위치에 좌하귀 화점이 될것이고, 여기서 root 밑으로 다음 수들이 뻗어나가서 가장 승률이 좋았던 자식의 위치를 찾는다. 그리고 결과 값을 찾아서 반환을 해준다고 생각하면 된다.(사실 알파고 알고리즘은 어떻게 생겼는지 모르지만, 예시를 들면 이렇게 알고리즘을 구성 했을 거라고 생각된다. 추측)

 

Tree 구조는 방대한 data에서 값을 찾는데 유용하다. 필요한 값을 찾는 방식은 2가지 방식이 있다.

DFS(Depth First Search)와 BFS(Breadth First Search)이다. DFS는 깊이를 먼저 찾고, BFS는 넓이 방향으로 먼저 찾는다. 

링크에 애니메이션으로 찾는 방식을 볼 수 있다. 글로 설명하면 DFS는 A - B - D - I - E -J 식으로 수직방향으로 먼저 값을 찾고, BFS는 A - B - C - D - E - F -G식으로 수평방향으로 먼저 값을 찾는다.

애니 링크 참조 : https://twpower.github.io/150-bfs-dfs-basic-problem-en

[Algorithm](EN) Basic DFS, BFS concept and problem

코드 링크 참조 : https://medium.com/front-end-weekly/using-map-method-on-tree-classes-f0600fc900c2

Using Map method on Tree Classes

사실 Tree 구조 찾는 방식을 아직 잘 이해 못해서 코드를 외웠다. ㅠㅠ 모르면 외우자는 식으로 덤비고 있다. ㄷㄷ 주입식 교육이다!!

 

#Javascript#codestates#datastructure#graph#Tree#DFS#BFS