자료구조) 2. 1) Graph

2. Graph, Tree, Binary Search Tree(BST, 이진탐색트리)

 1)Graph

  그래프는 직선, 곡선, 도형 등 그래픽적인 요소에 의해 시각화된 차트를 말한다.  컴퓨터과학에서 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. 정점들과 간선들로 서로간의 관계를 표현한 자료구조라고 할 수 있다. 두 정점간에 간선이 존재한다면 두 정점은 직접적인 관계를 가지고 있고, 두 정점간에 간선은 없지만 다른 정점들을 거쳐 도달할 수 있다면 두 정점은 간접적인 관계를 가지고 있다고 할 수 있다. 

그림으로 표현하자면 이렇게 표현 할 수있다. 파란원은 정점이고 각 원들 사이의 선은 간선이다. 간선중에는 한쪽으로만 화살표가 있는 선이 있는 반면, 양쪽 방향으로 화살표가 있는 선이 있다. 한쪽으로만 있는 선은 단방향이라고 말하고, 양쪽 다 있는 선은 무방향이라고 한다. 각 원들을 하나의 지역이라고 하면 무방향이 있다면 왕복티켓이 있다는 뜻이고 단방향은 편도티켓밖에 없다는 뜻이 된다.

 

  다음은 그래프 자료구조에 관한 용어들의 설명이다.

• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.

 이러한 특징을 가진 그래프 자료구조를 자바스크립트 언어로 표현하기 위해선 행렬과 리스트로 표현한다. 위 그림에서 아래에 하나있는 정점을 A, 왼쪽에 있는 정점을 B, 오른쪽에 있는 정점을 C라고 가정했을 때 행렬은 다음과 같은 표로 구현될 수 있다. 

to from	A	B	C
A	0	1	1
B	0	0	1
C	1	0	0

 자기자신에서 자기자신으로 가는 간선(자기루프)를 가진 정점이 없기 때문에 모두 0으로 표현이 되었고 A에서는 B, C 모두에게 접근이 가능 하기 때문에 1로 표현이 되어있다. B, C의 경우도 동일한 방식으로 적용되어 있는 것을 확인할 수 있다. 코딩을 할 때 행렬을 표현할 수 있는 자료형식에는 대표적으로 배열이 있다. 그래서 이 표를 배열로 바꾸어 보면 다음 코드가 된다.

const matrix = [[0, 1, 1],[0, 0, 1],[1, 0, 0]];

 from 에 해당하는 행의 순서대로 matrix배열의 인덱스가 정해진다. matrix[0]은 A에서 접근할 수 있는 간선의 정보를 담고 있다. matrix[1]은 B, matrix[2]는 C에 대한 정보를 담고 있다. matrix배열 안의 각 요소들은 해당 정점에서 모든 정점에 대한 간선의 정보를 의미하기 때문에 matrix배열의 길이와 matrix배열의 요소배열들의 길이는 같고 이는 정점의 갯수와 같다.

 

 리스트는 방향성에 대한 정보가 필요 없을때 사용된다. 행렬에서는 간선이 없는 경우 0이라고 표시가 된다. 하지만 방향성이 필요 없다면 이 0이라는 정보도 역시 필요없게 된다. 이때 행렬대신에 리스트를 사용하는 것이 더 메모리 사용에 있어서 효율적이다. 행렬은 불필요한 정보들도 포함하기 때문이다. 

출처 :  https://ipwag.tistory.com/92

 그림을 보면 초록색 네모는 각 정점들을 의미하고 오른쪽 노란 네모들은 그 정점들에서 접근 할 수있는 모든 정점들을 의미한다. 그리고 모든 경우의 수가 표현되었다면 null값을 마지막에 넣어 더이상 접근 할 수 있는 정점이 없다는 것을 표현했다.

const list1 = [[1, 2, 3],[0, 2, 4],[0, 1, 3],[0, 2, 4],[1, 3]]
//정점 0 에서 접근할 수있는 정점들은 list1[0] 안에 있다.

const list2 = [[1],[2],[0, 1, 3],[]]