[JavaScript] 자료구조 (3-2): 그래프(Graph)와 인접 리스트

0. 인트로

앞선 포스트에서 그래프는 정점 간의 관계를 나타내는 자료구조라고 했다. 그리고 정점 간의 관계를 나타내기 위하여 이용하는 것이 인접 행렬과 인접 리스트라고 했다. 이번 포스트에서는 인접 리스트가 무엇인지에 대해 알아보고 인접리스트를 클래스를 이용하여 구현해볼 것이다.

1. 인접 리스트란?

인접 리스트는 정점과 정점 간의 관계를 리스트로 나타낸 것이다. 하지만 자바스크립트에서는 리스트라는 데이터 형태가 없다. 따라서 리스트 대신에 객체로 대체한다. 객체의 속성 값을 중요한 순서대로 나열할 수도 있고, 그냥 나열할 수도 있다. 사실 우선순위별로 정렬한다면 힙(heap)이나 큐(queue)를 쓰는 것이 낫다고 합니다. 한편, 인접 리스트는 인접 행렬에 비하여 메모리가 적게 드는 특징이 있다. 사실 생각해보면 당연하다. 인접 행렬은 엘리먼트 개수가 정점 개수의 제곱이기 때문이다.

2. 인접 리스트 구현

아래는 자바스크립트의 클래스를 이용하여 인접 리스트를 구현한 것이다.

// undirected graph (무향 그래프)
// adjacency list (인접 리스트)
class GraphWithAdjacencyList {
	constructor() {
		this.vertices = {};
	}

	addVertex(vertex) {
		// TODO: 정점을 추가합니다.
		// 넘겨받은 인자(정점)은 키가 되며, 빈 배열을 값으로 할당합니다.
		// 이미 존재하는 정점이라면, 덮어 씌워지지 않아야 합니다.
		if (vertex in this.vertices) {
      this.vertices[vertex] = this.vertices[vertex];
    } else {
      this.vertices[vertex] = []
    }
	}

	contains(vertex) {
		// 인자로 넘겨받은 정점의 존재여부를 반환합니다.
		return !!this.vertices[vertex];
	}

	addEdge(fromVertex, toVertex) {
		// TODO: 간선을 추가합니다.
		// - fromVertex의 인접 리스트에 toVertex를 추가하고
		// - toVertex의 인접 리스트에 fromVertex를 추가합니다.
		// 넘겨받은 2개의 정점 모두 존재하는 정점이어야 합니다.

		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return;
		}

		if (!this.hasEdge(fromVertex, toVertex)) {
      // TODO
      this.vertices[fromVertex].push(toVertex)
      this.vertices[toVertex].push(fromVertex)
		}

		
	}

	hasEdge(fromVertex, toVertex) {
		// 만약 정점(fromVertex)이 존재하지 않는다면
		if (!this.contains(fromVertex)) {
			// false를 반환합니다
			return false;
		}
		// 존재한다면 해당 정점의 리스트에 toVertex가 포함되어있는지 반환합니다
		return !!this.vertices[fromVertex].includes(toVertex);
	}

	removeEdge(fromVertex, toVertex) {
		// TODO: 간선을 삭제합니다.
		// 인자로 넘겨받은 두 정점이 모두 존재한다면
		// - fromVertex의 인접 리스트에 있는 toVertex를 삭제하고
		// - toVertex의 인접 리스트에 있는 fromVertex를 삭제합니다.

		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return;
		}
    // 첫 번째 정점의 인접 리스트에 두번째 정점이 있을 경우
		if (this.hasEdge(fromVertex, toVertex)) {
			const index = this.vertices[toVertex].indexOf(fromVertex);
			this.vertices[toVertex].splice(index, 1);
		}
		// TODO:  두번째 정점의 인접 리스트에 첫번째 정점이 있을 경우
    if (this.hasEdge(fromVertex, toVertex)) {
			const index = this.vertices[fromVertex].indexOf(toVertex);
			this.vertices[fromVertex].splice(index, 1);
		}
	}

	removeVertex(vertex) {
		// TODO: 정점을 삭제합니다.
		// 인자로 넘겨받은 정점(A)이 존재한다면
		// - 이 정점(A)을 삭제함은 물론,
		// - 다른 모든 정점들의 리스트를 순회하며 넘겨받은 정점(A)과 이어져 있는 간선을 제거합니다
		if (this.contains(vertex)) {
     while (this.vertices[vertex].length > 0) {
				this.removeEdge(this.vertices[vertex][0], vertex);
			}
			// 최종적으로 해당 정점을 삭제합니다
			delete this.vertices[vertex];
		}
		
	}
}