그래프 (Graph)

그래프란 ?

그래프란 노드들(vertex)와 그 노드들을 연결하는 간선(edge)를 하나로 모아놓은 비선형 자료구조이다.

종류

그래프는 방향성에 따라 무방향 그래프와 단방향 그래프로 나눌 수 있고 가중치를 할당하는 가중치 그래프가 있다.

단방향 그래프

무방향 그래프

가중치 그래프

구현 방식

그래프는 인접 행렬(Adjacency matrix)과 인접 리스트(Adjacency list) 방식으로 구현할 수 있다.

인접 리스트

인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법이라고 하며, 그래프 내에 적은 숫자의 간선만을 가지는 경우에 용이하다고 한다. 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다. 배열이나 연결리스트 등을 이용해서 구현이 가능하다. 특징은 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하여 공간 효율성은 우수하지만 각 정점들의 연결 여부 확인을 위해 O(v)의 시간 복잡도를 가진다.

인접 행렬

인접 행렬은 정점들을 2차원 배열로 구현한 것이다. 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프의 경우에 용이하며, 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하고, 특정 노드의 인접 노드들을 탐색하기위해선 모든 노드들을 확인해야하지만, 정점간의 연결여부 확인 시 O(1)의 시간을 요구한다.

BigO

인접 리스트 구현

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter((v) => v !== v2);
    this.adjacencyList[v2] = this.adjacencyList[v2].filter((v) => v !== v1);
  }

  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacencyVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacencyVertex);
    }
    delete this.adjacencyList[vertex];
  }
}