4.9Graphs

Graphs

A graph data structure consists of a finite (and possibly mutable) set of vertices(정점) or nodes or points, together with a set of unordered pair of these vertices for an undirected graph or a set of ordered paris for a directed graph.

여기서 그래프는 우리가 일상 생활에서 종종 얘기하는 시각적 차트를 의미하는 것이 아니라, 데이터 구조다. 위의 정의를 간단하게 요약하면, 그래프는 연결된 노드들이다. 예를 들어, 아래와 같이 노드들이 있고 연결되어 있다면 그래프 데이터 구조다.

이미지 출처 : #

그래프는 SNS, 위치 정보, 내비게이션, 파일 시스템 최적화 등에서 쓰인다. 또, 추천 시스템에서 "당신이 좋아할 만한 컨텐츠" 등을 선별하는데도 쓰인다.

그래프의 용어와 종류

그래프 데이터 구조에서 자주 쓰이는 용어들을 짚고 넘어가자.

• Vertex(정점): 그래프 구조에서 노드를 일컫는 말
• Edge(변): 노드와 노드 간의 연결선
• Weighted / Unweighted(가중): 정점 간의 간격에 가중치가 다른 그래프가 Weighted 그래프다.
  • 예를 들어, A 지점과 B 지점의 간격은 90km, B지점과 C 지점은 40km라고 표시한 그래프 구조는 Weighted 그래프다.
• Directed / Undirected(유향/무향): 방향이 있는 그래프와 없는 그래프. 즉, 특정 정점로부터 다른 정점로 갈 수 있는 방향이 단방향이면 Directed 그래프다. 정점간 양방향 어디로 갈 수 있다면 Undirected 그래프다.
  • 예를 들어, 인스타그램 팔로우 구조는 A가 B를 팔로우 하더라도 B가 A를 팔로우하지 않을 수도 있다. 이런 경우 유향 그래프(Directed)다. 반면, 페이스북은 서로 친구를 맺는 방법밖에 없다. 이런 경우 무향 그래프(Undirected)다.

그래프 구현의 두 방법

그래프를 코드로는 어떻게 구현할 수 있을까? 두 가지 접근 방법이 있다.

1. Adjacency Matrix(인접 행렬)

각 정점들을 행과 열에 둔 행렬을 만들면 그래프를 표현할 수 있다. 아래는 단순화된 예시여서 무향 그래프이지만, 유향 그래프나 가중치도 표현 가능하다.

이미지 출처 : #

2. Adjacency list(인접 목록)

각 인덱스(또는 키)에 정점들을 두고, 어떤 정점들과 연결되는지 중첩된 배열로 표현할 수 있다. 즉, 해시 맵을 활용하는 것이다.

이미지 출처 : #

인접 행렬과 인접 목록은 시간 복잡도 측면에서 많은 차이가 난다. 목록의 경우 새로운 정점이 생기면 배열을 하나 추가하면 되지만, 행렬은 행과 열이 하나 더 추가되므로 훨씬 큰 비용이 든다. 또, 모든 연결을 순회하는데에도 목록은 연결이 실재하는 데이터만 저장하는데 비해 행렬은 0으로 연결이 없는 관계도 저장하므로 시간이 더 든다.

단, 특정 연결을 찾는데는 행렬이 훨씬 빠르다. 예를 들어, 위의 이미지에서 C와 E를 잇는 연결이 있는지 찾는다면, 행렬에선 바로 C와 E의 관계를 볼 수 있지만 목록에선 우선 C를 찾고, C 내부의 배열을 또 순회해야 한다.

우리는 이번 포스트에서 인접 목록으로 가중치가 없는 그래프를 구현한다. 실제 세상에서 쓰는 데이터 중 상당수는 정점 수에 비해 연결이 많지 않다. 따라서, 연결이 없다는 것도 모두 저장해야하는 인접 행렬에 비해 더 효율적인 목록을 구현하는 것이 더 유용한 경우가 많다.

가중치가 있는 그래프는 이후 포스트인 다익스트라 알고리즘에서 구현한다.

인접 목록으로 그래프 구현하기

1. Graph와 Vertex 추가하기

우선 Graph 클래스와 vertex(정점)을 구현하자. 사실상 정점을 추가하는 것은 그냥 객체에 해당 이름의 정점을 키로 하는 빈 배열을 추가하는 것이다. 배열에 들어갈 요소들은 이후 변(Edge)이 생기며 들어간다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  addVertex(vertex){
    if(!this.adjacencyList[vertex]){
      this.adjacencyList[vertex] = [];
    }
  }
}

2. 변 추가하기

변을 추가하려면 변으로 연결되는 두 개의 정점을 받아야 한다. 우리는 무향의, 가중이 없는 그래프를 구현하고 있으니, 두 개의 정점을 키로 하는 배열에 각각 상대의 정점을 추가하면 된다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  addVertex(vertex){
    // ...
  }
  addEdge(v1, v2){
    // 에러 핸들링 로직이 있으면 더 좋다!
    // ex. v1, v2 각각의 키가 없는 경우, 중복값이 이미 있는 경우
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
}

3. 변 제거하기

추가할 때와 마찬가지로 양쪽의 정점을 키로 하는 배열에서 상대를 빼면 된다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  addEdge(v1, v2){
    // ...
  }
  removeEdge(v1, v2){
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
     this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
  }
}

4. 정점 제거하기

정점을 받아 제거하는 메소드를 추가하자. 인접 목록의 키에서 해당 정점을 제거하는 것 뿐 아니라, 다른 정점의 배열에도 해당 정점이 있으면 제거해야 한다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  removeVertex(vertex){
    while(this.adjacencyList[vertex].length){
      const adjacentVertex = this.adjacencyList[vertex].pop(); // 연결된 정점을 하나씩 제거하며 반환
      this.removeEdge(vertex, adjacentVertex); // 반환받은 연결된 정점과 연결하는 변을 제거
    }
    delete this.adjacencyList[vertex]; // 키를 제거
  }
}