Data Structure 2

황순은·2021년 4월 25일

복습

목록 보기

2/3

그래프(Graph)?

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조.

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

서울, 대전, 부산 3개의 vertex가 있고, 서울 — 대전, 대전 — 부산, 부산 — 서울의 간선이 있으므로 서로 연결되어있다고 할 수 있다.

그래프 용어

정점(vertice): 노드(node)라고도 하며 정점에는 데이터가 저장된다. (value)
간선(edge): 노드간의 관게를 나타낸다.
무향그래프(undirected graph): 위의 예시에서 알 수 있듯 정점과 정점사이의 간선에는 양쪽으로 연결되어 있는 것을 무향(undirected)라고 하며 반대로 한쪽으로만 연결되어 있다면 단방향(directed)이라고 한다.
진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입하고 진출하는 간선이 몇개인지 나타낸다.
인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두정점은 인접한 정점이라 할 수 있다.
자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기루프를 가졌다 표현하며, 다른 정점을 거치지 않는다는 것이 특징이다.
사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다. 위의 예시에서는 서울 ⇒ 대전 ⇒ 부산 ⇒ 서울 으로 이동이 가능하므로 사이클이 존재하는 그래프이다.

그래프의 표현방식

인접 행렬

인접 행렬은 노드를 2차원 배열로 만든것이다. 완성된 배열의 모양은 표 or matrix형식을 하고 있으며 A라는 정점과 B라는 정점이 이어져 있으면 1, 그렇지 않다면 0으로 표시한다.

let matrix = new Array(3).fill(0).map((y) => new Array(3).fill(0));
/*
   A  B  C    // A => C //      A  B  C
A [0, 0, 0]   // B => A //   A [0, 0, 1]
B [0, 0, 0]   // B => C //   B [1, 0, 1]
C [0, 0, 0]   // C => A //   C [1, 0, 0]
*/

두 정점 사이에 관계가 있는지, 없는지 확인할 때 용이하다.
위의 그래프에서 A ⇒ B (0, 1)의 간선은 존재하지 않고, A ⇒ C (0, 2)의 간선은 존재한다.
가장 빠른 경로를 찾을때 주로 사용된다

인접 리스트

인접 리스트는 노드를 리스트로 표현한것이다. 주로 정점의 리스트 배열을 만들어 관계를 설정해서 구현한다.

/* 인접 행렬
   A  B  C    // A => C //      A  B  C
A [0, 0, 0]   // B => A //   A [0, 0, 1]
B [0, 0, 0]   // B => C //   B [1, 0, 1]
C [0, 0, 0]   // C => A //   C [1, 0, 0]

   인접 리스트
A => B (0, 1) // false;
B => A (1, 0) // true;
A => C (0, 2) // true;
B => A => C (1, 0), (0, 2) // true
*/

인접 행렬은 연결가능한 모든 경우의 수를 저장하기 때문에 메모리를 많이 차지한다.
인접 행렬보다 인접 리스트방식이 메모리를 더 효율적으로 사용할 수 있다.

트리(Tree)?

데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조

트리는 데이터를 순차적으로 나열시킨 형태인 선형 구조가 아닌, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비 선형구조로 되어 있고, 계층적으로 표현이 되며 아래로만 뻗기 때문에 사이클없는 하나의 연결 그래프다.

class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
}