[알고리즘] 그래프 (자바스크립트)

그래프

소개

그래프는 유한하고 변할 수 있는 꼭지점이나 노드, 점들의 집합으로 이루어진 자료구조이다. 넓게 보면 트리 구조에 속하지만, 시작점이나 진입점들이 존재하지 않고 오로지 같은 레벨의 노드만 존재한다. 꼭지점 집합에 순서 규칙이 존재하는 경우 유방향 그래프, 존재하지 않는 경우 (양방 통행이 가능한 경우) 무방향 그래프로 분류한다. 또한 연결 관계에 가중치를 부여할 수도 있다.

 

그래프는 노드와 연결관계로 얽혀있는 메쉬 형태 구조라고 해도 될 듯 하다. 또한 기존에 칭하던 노드를 "Vertex (정점)"으로, 노드 간의 연결관계를 "Edge (간선)"이라고 부른다.

 

용례

• SNS 관계망
• 지도 기능 : 방향 안내, 위치, 길 찾기 등
• 웹 라우팅 : 인터넷 생태계나, 특정 웹사이트의 연결 관계
• 추천 알고리즘 : 좋아할 만한 상품, 이런 것은 어떠세요? 등

---

 

구현

그래프 구조를 구현하기 위해서는 노드들을 어떤 형식으로 연결해주어야 할까? 일반적으로 인접 행렬과 인접 리스트를 사용한다.

 

인접 행렬은 각 노드를 X,Y 레이블로 갖는 정사각행렬로, 인접한 노드와의 관계를 알 수 있다. 또한 노드가 늘어날 때마다 해당 노드에 대한 모든 노드의 관계성이 추가되기 때문에 공간을 더 많이 차지한다. 따라서 넓게 퍼진 데이터를 관리할 때 적합한 알고리즘 방식은 아니다. 그러나 특정 간선이 있는지 확인할 때는 인접 리스트보다 빠르게 확인이 가능하다는 특징이 있다.

 

인접 리스트는 정사각 행렬 대신 배열에 저장해서 특정 인덱스 노드와 연결되어 있는 노드 정보를 2차원 배열 형식으로 저장한다. 키-값 형태의 객체로도 노드 관계 정보를 담을 수 있다.

 

인접 리스트를 활용한 구현 (무방향)

아래는 인접 리스트 메서드를 위한 스켈레톤 클래스 코드이며, 메서드의 구현 자체가 그리 난이도가 있지는 않다.

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

 

addVertex 메서드

그래프에 노드(정점)을 추가하는 메서드이다. 정점의 이름을 인접 리스트의 키로 입력받는다. 값으로는 빈 배열이 주어진다.

  addVertex(key) {
    if (!this.adjList[key]) this.adjList[key] = [];
  }

 

 

removeVertex 메서드

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

 

addEdge 메서드

정점간의 연결 관계성을 추가하는 메서드이다. 무방향 특성을 가져 양방이동이 가능하기 떄문에, 두 정점을 입력받아 해당 정점의 값 리스트에 접근하여 서로의 정점을 넣어준다.

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

 

removeEdge 메서드

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