[TIL]Graph, Tree, BST

1) Graph

• 개념

  vertex, edge, degree & indegree & outdgree

  그래프는 자유로운 비선형 자료구조로, 하나의 지점을 나타내는 vertex(정점, node)와 vertex를 연결하는 edge(간선)로 구성된다. Vertex는 자체 루프(self-loop)를 이룰 수 있기 때문에 시작과 끝의 순환이 가능하다.

  하나의 vertex와 이어진 vertex를 인접vertex라고 하며, 인접vertex의 수를 degree라고 한다.

  • 코드로는 아래처럼 표현할 수 있다.

    hasEdge(fromNode, toNode) {
        for(let i = 0; i < this.edge.length; i++) {
          if(this.edge[i][0] === fromNode && this.edge[i][1] === toNode) {
            return true;
          } else if (this.edge[i][1] === fromNode && this.edge[i][0] === toNode) {
            return true;
          } else {
            return false;
          }
        }
      }

• 사례

  • 내비게이션이나 지하철 노선도처럼 최단거리를 구할 때, 최소비용 찾기, 물류나 택배의 동선 최적화

• Method

  • addNode(node) - 그래프에 노드를 추가한다.
  • addEdge(fromNode, toNode) - fromNode와 toNode 사이에 간선을 추가한다.
  • removeNode(node) - 그래프에서 노드를 삭제한다.
  • removeEdge(fromNode, toNode) - fromNode와 toNode 사이에 간선을 삭제한다.
  • hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환한다.
  • contains(node) - 그래프에 해당 node가 존재하는지 여부를 반환한다.

• 종류

  (1)무방향 그래프(Undirected Graph)

  Edge에 의해 연결된 2개의 vertex가 대칭일 수 있다는 의미다.

  (2)Directed Graph

  • 방향성이 있는 그래프는 비대칭 관계를 의미한다.
  • 이 경우 vertex로 들어오는(→) edge의 수를 in-dgree(진입차수), 나가는 수(→)를 out-dgree(진출차수)라고 한다.

• 탐색 방식

  (1) 깊이우선탐색(Depth First Search, DFS)

  • 그래프는 비선형 자료구조이기 때문에 순차적 탐색이 불가능하여 전체를 탐색할 수 있는 별도의 알고리즘이 필요하다. 그 중 한 방법인 깊이우선탐색은 한 방향을 깊게 탐색하면서 vertex가 존재하지 않으면 다시 돌아나온다. 하나의 child node를 방문하여 그 child, 또 그 child를 끝까지 탐색하는 식이다. 이때 탐색 히스토리를 저장했다가 다시 돌아오는 백트래킹을 해야 하므로 스택을 활용한다. Node를 담았다가 꺼내서 출력하고 child node를 담으며, 한 번 담았던 node는 다시 넣지 않는다.

  • 반드시 출발점이 0일 필요는 없다.

  • 깊이우선탐색 방식에서는 재귀함수를 사용하면 훨씬 간결하게 코드를 구성할 수 있다. 한 Node에 방문하면 데이터를 출력하고 자식들을 순서대로 재귀 호출한다. 호출받은 자식은 자신을 출력하고 다시 자신의 자식들을 재귀 호출한다. 데이터 반환 전에 자식을 먼저 호출하기 때문에 재귀가 가능하다.

  • 이진트리를 검색하는 방식인 inorder, preorder, postorder도 여기에 속한다.

    (2) 넓이우선탐색(Breadth First Search, BFS)

  • 레벨 단위의 검색법으로 시작점에서 자신의 child node를 다 방문한 뒤 그 다음 레벨의 자식들을 방문한다.

  • 큐의 특성을 이용하여 여러 방향으로 뻗어나가는 edge를 넓게 훑는다.

  • 깊이우선탐색에 비해 균일한 탐색속도를 보이지만 tree처럼 레벨이 내려갈수록 데이터의 범위가 넓어질 경우, 탐색대기 node가 많아지며 메모리 사용량이 늘어나고 필요없는 연산이 많아질 수 있다.

    *두 방식 모두 목적지 없이 모든 값을 탐색할 때도 쓰인다.

    (3) 그외

  • 프림 알고리즘

    그래프의 모든 점을 최소의 비용으로 연결하는 미니멈스패닝트리(MST)를 구하는 알고리즘. 하지만 모든 vertex를 연결하는데 총비용이 낮은 결과물을 만들뿐, 특정 vertex와 vertex간의 최단거리는 보장하지 않는다. 통신, 전력회선, 수도관 등의 기반시설이나 물류, 택배 등에서 쓰인다.

  • 다익스트라(Dijkdtra) 알고리즘

    한 지점에서 다른 지점까지의 최단거리를 구한다(Single source shortest path, SSP).

• 구현 방식

  (1) 인접리스트방식(Adjacency List)

  • Vertex 객체 안에 인접vertex를 list로 저장한다.

  • 하나의 vertex를 기준으로 탐색할 때, 그래프에 edge가 적을 때 사용한다.

  • 이차원 배열에 표현. 표 연결된 노드는 1 연결없으면 0

    (2) 인접행렬방식(Adjacency Matrix)

  • 2차원 배열에 모든 vertex의 연결관계를 표현한다.

  • Edge를 기준으로 탐색할 때, 그래프에 edge가 많을 때 사용한다.

  • Edge가 서로 연결되므로 edge의 갯수가 m개라면 총 node의 갯수는 2m개가 된다.

    *인접리스트방식은 특정 node에 접근하기 위해 리스트를 처음부터 확인해야하지만, 인접행렬방식에서는 한 번의 접근으로 확인 가능하다.

2) Tree

• 개념

  • Tree는 그래프의 한 형태로, node로 구성된 계층적 자료구조다. 최상위 node(root)를 만들고, root node의 child node를 추가하고, 그 child node가 다시 부모가 되어 child node를 추가하는 방식으로 구현할 수 있다.
  • node : tree의 구성요소
  • root : 최상위에 존재하는 node
  • depth : root를 기준으로, 다른 node로 접근하기 위한 거리
  • height : tree 전체의 최대 depth 값
  • sibling : 같은 depth에 존재하는 node들은 sibling 관계(형제node)다.
  • edge : node와 node를 잇는 선
  • leaf : 자식이 없는 node(단말node).
  • subtree : tree의 일부를 이루는 tree

• 종류

  방향성이 있으면 Directed Tree, 없으면 Undirected Tree.

• 트리와 그래프

  1. 그래프는 2개 이상의 경로를 가질 수 있고, node 간의 양방향 경로를 가질 수도 있지만

     트리는 두 개의 정점 사이에서 반드시 1개의 경로만을 가진다.

  2. 그래프는 self-loop, loop, circuit이 모두 가능하지만

     트리는 세 가지 모두 불가능하다.

  3. 그래프에는 root node의 개념이 없지만

     트리는 한 개의 root node가 존재하며 모든 자식 node는 한 개의 부모 node를 가진다.

  4. 그래프에는 부모-자식 관계의 개념이 없지만

     트리는 모두 부모-자식 관계이므로 top→bottom 또는 bottom→top의 흐름을 가진다.

  5. 그래프의 순회는 DFS나 BFS로 이뤄지고

     트리의 순회는 pre-order, in-order, post-order 중의 하나로 이뤄진다. 이 세 가지 경우는 모두 DFS/BFS에 속한다.

  6. 그래프는 cyclic 혹은 acyclic이지만

     트리는 DAG(Directed Acyclic Graphs, 사이클이 없는 방향 그래프)의 한 종류다.

  7. 그래프는 크게 방향 그래프와 무방향 그래프로 나뉘고,

     트리는 이진트리, 이진탐색트리, AVL트리 등으로 나뉜다.

  8. 그래프의 간선 유무는 그래프마다 다르고,

     트리의 간선은 항상 '정점의 개수 -1'이다.

  9. 그래프는 네트워크 모델이며

     트리는 계층 모델이다.

2-1) Binary Tree(이진트리)

• 개념

  • 하나의 부모노드가 최대 2개의 자식노드만 가지는 트리. 자식노드 역시 최대 2개의 자식을 가진다.

• 특징

  • 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 자리한다. *루트노드를 삭제했을 때 새롭게 루트노드가 되는 건 왼쪽이나 오른쪽에서 가장 가까운 숫자다. 이렇게 해야 전체 트리의 변화가 가장 적게 일어난다.
  • 배열보다 평균 탐색속도가 빠르다.
  • 정리가 잘 되어 있다면 최악의 경우에도 최대높이값 만큼만 비교하면 자료를 찾을 수 있다.
  • 데이터의 추가, 삭제도 규칙을 따라야 한다.

• 사례

  • 데이터를 정해진 규칙에 따라 저장하고 '빠르게' 찾는 '검색'용도로 많이 사용한다. (예: 업다운게임 앱)

• 종류

  1) 정이진트리(Full Binary Tree)

  모든 노드에 자식이 2개씩 있거나 아예 없는 경우

  2) 포화이진트리(Perfect Binary Tree)

  값이 채워질 수 있을 만큼 다 채워진 상태로, 층을 늘리지 않으면 더 채울 수 없는 경우

  3) 완전이진트리(Complete Binary Tree)

  어디서부터 값을 찾는지가 중요하다. 맨 아래 오른쪽 노드가 비어있는 경우

• 순회의 종류

  1) 전위 순회(Preorder Traversal): 부모 → 좌 → 우

  2) 중위 순회(Inorder Traversal): 좌 → 부모 → 우

  3) 후위 순회(Postorder Traversal): 좌 → 우 → 부모