Udemy - 그래프(Graph)

그래프

그래프는 트리에서 한 단계 더 나아가, 같은 계층 간의 노드끼리도 연결될 수 있는 하나의 자료구조다. (물론 트리도 그래프의 한 종류라고 볼 수 있다)

지도, SNS, 라우팅, 연관 데이터 추천 등등 그래프 자료구조는 정~~말 많은 곳에서 활용된다.

그래프에서 사용되는 용어

1. 정점 (Vertex)

   ⇒ 하나의 독립적 노드들을 의미한다.

2. 간선 (Edge)

   ⇒ 노드 사이의 연결을 의미한다.

그래프의 종류

1. 무방향 그래프

   ⇒ 특정한 방향성 없이, 모든 노드들이 서로 양방향으로 연결된 그래프다.

2. 방향 그래프

   ⇒ 방향성이 존재한다. 따라서 모든 노드들이 상호 연결되어있는 것이 아니라 한 노드가 특정 노드를 일방적으로 연결하고 있는 그래프다.

3. 가중 그래프

   ⇒ 간선(Edge)에 특정한 값 또는 의미가 부여된 그래프를 의미한다. (지도가 대표적이다. 각 노드(목적지) 간에 거리라는 특정값이 존재하기 때문이다)

4. 비가중 그래프

   ⇒ 위와 반대로 기본적인 간선을 기반으로 하는 그래프다. 간선에 특정 값이 부여 및 할당되어 있지 않다.

---

그래프의 활용

이제 본격적으로 그래프를 코드로써 어떻게 활용할 수 있는지에 대해 정리해보도록 하겠다.

인접 행렬

기본적으로 행과 열에 맞춰 정보를 저장하는 방식이다.

위에 제시된 그래프가 인접행렬로 표현된다면 바로 위 표와 같은 형태가 된다. 각 정점들 간의 연결을 1,0 또는 true or false를 통해 표현한 것이다.

인접 리스트

우리가 흔히 사용하던 배열을 활용한 방법이다.

위의 사진과 같이 각 정점별 직접적으로 연결 되어있는 정점(노드)들을 배열 또는 해시테이블로써 표현한 것이다.

만약 모든 정점들의 값이 숫자라면 그냥 배열과 배열의 인덱스를 통해 그래프를 표현할 수 있지만, 정점의 값이 숫자가 아닌 경우에는 index로 각 배열이 가리키는 정점값을 표현할 수 없기에, 주로 해시테이블을 사용한다.

두 그래프 표현 방식의 차이점은 뭘까?

• |V| : 정점의 개수
• |E| : 엣지의 개수

이를 정리하자면..

인접 행렬	인접 리스트
공간을 많이 차지한다	공간을 적게 차지한다
모든 간선을 탐색하는데 느리다	모든 간선을 탐색하는데 빠르다
특정 간선을 탐색하는 것은 빠르다	특정 간선을 탐색하는 것은 느리다

이러한 이유에 따라, 우리는 대부분 인접 리스트를 활용하게 된다.
앞으로 알고리즘 문제를 풀 때에도 우리는 인접 리스트를 거의 대부분 사용하게 될 것이다.

---

인접 리스트를 활용한 Add

특정 정점(vertex)을 추가하는 Add 메소드 코드를 작성해보도록 하겠다.

class Graph {
  constructor() {
    this.list = {};
  }
  addVertex(v) {
    // 매우 간단하다. 해당 해시테이블에 v 키가 없으면 빈 배열을 밸류로 주며 만들어주면 된다.
    if (!this.list[v]) this.list[v] = [];
  }
}

이번엔 무방향 그래프에서 간선(Edge)를 추가하는 Add 메소드다.

class Graph {
  constructor() {
    this.list = {};
  }
  addEdge(v1, v2) {
    this.list[v1] = v2;
    this.list[v2] = v1;
  }
}

---

인접 리스트를 활용한 Remove

특정 정점(Vertex)과 간선(Edge)를 삭제하는 Remove 메소드다.

class Graph {
  constructor() {
    this.list = {};
  }
  removeEdge(v1, v2) {
    this.list[v1] = this.list[v1].filter((v) => v !== v2);
    this.list[v2] = this.list[v2].filter((v) => v !== v1);
  }
  removeVertex(v) {
    while (this.list[v].length) {
      const tempVertex = this.list[v].pop;
      this.removeEdge(v, tempVertex);
    }
    delete this.list[v];
  }
}

---