Graph

코공·2020년 12월 7일

Graph JavaScript

오늘은 데이터 자료구조의 그래프를 알아보자 이말이야.

Graph

그래프는 데이터 자료구조 종류 중 하나이다.
그러면 그래프는 어떻게 자료를 정리할까? 그림을 살펴보자.

그래프는 위 사진처럼 각 노드(데이터)들을 연결해 주는 선(Edge)가 있다.

요런 자료는 실생활에서 어디서 쓰냐?
지하철 노선도나, 네비게이션이 길을 알려줄 때 쓴다.
각 데이터들은 연결된 edge로 최단 경로나 최소 환승 등을 알려준다고 한다.

Graph 특징들

Graph 구성

1. Vertex(Node) - 혹은 정점이라고도 한다.

2. Edge - 간선이라고도 한다. vertex와 vertex를 이어주는 선이 있다.

Undirected-무방향 그래프 / directed -방향 그래프

그래프는 2가지로 나뉜다. Undirected-무방향 그래프 / directed -방향 그래프

1. Undirected-무방향 그래프
왼쪽 사진처럼 Edge에 방향 표시가 없는 것이 무방향 그래프다.
무방향 그래프는 Edge로 이어진 Vertex간의 이동이 자유롭다.
내가 밑에서 구현할 코드는 무방향 그래프이다.

2. directed -방향 그래프
오른쪽 사진처럼 방향 표시가 있는 것이 방향 그래프.
당연 편도로만 이동이 가능하다.

Graph의 Cycle

그래프는 자기가 만드는 그래프에 따라 Cycle(출발한 곳에서 나가 다시 돌아올 수 있는 구조)를 만들 수 있고, 심지어 self loof도 가능하다.

일러스트로 30초 뚝딱하면 만들 수 잇는 사진. 하지만 데스크탑을 왔다 갔다 해야 해서 매우 불편하다.

A의 Edge를 잘 보면 집을 나갔다가 다른 vertex를 들리고 다시 집으로 돌아오는 구조를 볼 수 있다. 이런 모양이 Cycle.

오른쪽 위와 같이 self loof 구조도 있다.

Graph의 degree

Graph에는 degree가 존재한다.

왼쪽 사진
무방향 그래프에서 하나의 정점에 인접한 정점의 수를 말한다.
제일 왼쪽 Vertex는 2개의 degree를 가지고 있는 것.

오른쪽 사진
방향 그래프에서는
in-degree 방향 그래프에서 외부에서 오는 간선의 수
out-degree 방향 그래픙에서 외부로 향하는 간선의 수
vertex A는 in이 2개, out이 1개인 것.

Graph의 가중치

가중치 그래프(Weighted Graph)
간선에 비용이나 가중치가 할당된 그래프
경로를 탐색할 때 들여지는 시간이나 비용 등을 나타낼 수 있따.

만약 A에서 D로 가고 싶으면 A-B-D는 가중치가 총 70이지만
A-C-E-D는 총 가중치가 30이니까, 만약 최소 비용으로 D를 가고 싶다면
요 루트로 가자.

Graph의 2가지 구현 방법

인접 행렬(Adjacency Matrix) 방식

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다.
0과 1을 이용한 정수 행렬로 표현할 수 있다.
obj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0
항상 n^2라는 공간 복잡도가 존재한다.

장점 :
구현이 쉽다.
단순 노드끼리의 연결을 확인하고 싶을 때는 O(N)이라는 시간 복잡도 안에서 해결 된다.
간선의 추가와 삭제가 빈번히 일어나는 경우에는 이 방식이 효율적이다.

단점 :
'a'라는 노드에 연결된 모든 노드를 찾을 때는 총 O(V)의 시간이 걸린다는 점
간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다.
정점의 추가 삭제에는 효율적이지 않다.

인접 리스트(Adjacency List) 방식

가장 일반적인 방식이라고 한다.
linked list랑 비슷하다.
그래프에 존재하는 최대 간선의 수는 O(n+e)이다.

장점 :
vertex의 번호만 알게 된다면 이 번호를 배열의 인덱스로 해서, 각 vertex의 리스트에 쉽게 접근할 수 있다.
정점의 추가 삭제가 빈번히 일어나는 경우에는 이 방식이 효율적이다.

단점:
a가 b와 연결되어 있는 것을 확인하려면 a의 리스트를 순회해야지 b와 연결되어 있는지 확인이 가능하다.
이 경우, O(v)의 시간 복잡도를 갖는다.
반면 인접 행렬이라면, [a][b]가 1인지 0인지만 확인하면 가능하기에 이럴 때 인접행렬은 O(1)만큼만 걸린다.

Graph 메소드

addNode : 그래프에 노드 추가하기
contains: 그래프에 해당 노드가 있는지 확인
removeNode: 노드 삭제하기
hasEdge: 노드와 노드 사이에 엣지가 있는지 확인
addEdge: 노드와 노드 사이에 엣지 추가
removeEdge: 노드와 노드 사이의 엣지 삭제

Graph 코드

배열로 구현할 예정이다. 그리고 무방향 그래프이다.

1. 기본 뼈대

부트캠프가 만들어 준 뼈대이다. 착하네?

2. addNode

너무 작나?

  addNode(node) {
    this.nodes[node] = this.nodes[node] || []; //배열로 만들 예정.
 
 예시로 이렇게 만들었다고 치자
   nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }

3. contains

4. removeNode

   nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     
     여기서 1을 삭제하고 싶으면
     우선 nodes[1]에 있는 [0]을 먼저 지우자. removeEdge로.
     그 이후 nodes[1]는 객체니까 delete로 지우자.

5. hasEdge

   nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     
   여기서 1의 간선을 확인하고 싶으면
   nodes[1]에 0이 있고, nodes[0]에도 1이 있는지 확인하자.
   그래야 뜨루!