[Algorithm] Javascript Graph 자료구조 인접 리스트(Adjacency List) 구현하기

 

 

 

Graph 인접 리스트란?

 

인접 리스트(Adjacency List)는 각 정점이 어떤 정점과 인접하고 있는지를 리스트 형태로 표현한다. 각 정점은 하나의 리스트를 가지게 되며 인접한 다른 정점을 리스트에 담고 있다. 

 

서울 - 부산 - 제주, 3개의 정점이 있다고 가정하자. 서울은 부산으로의 간선을 가지고, 부산은 제주로의 간선을 가지며, 제주는 서울로의 간선을 가지게 된다.

 

위 그래프를 인접 리스트로 구현하면 다음과 같다. 

 

 

그래프 자료구조에서 인접 리스트는 객체로 구현된다. 각 정점은 Key값이 되고 정점과 연결된 간선들의 정보는 배열로 Value 값이 된다.

 

 

굳이 인접행렬을 사용하는 이유?

 

그래프 자료구조에서 정점과 간선의 정보를 담기 위해서 일반적으로 인접행렬을 사용한다. 하지만 인접행렬의 가장 큰 단점은 비효율적인 메모리 사용이다. 

인접행렬의 경우 정점에서 연결 가능한 모든 경우의 수를 저장하는 2차원 배열이기 때문에 그래프 정점과 간선의 정보를 담기 위해 상대적으로 많은 메모리를 사용하게 된다. 따라서 인접 리스트를 구현해서 퀵 하게 그래프 자료구조를 구현할 수 있다.

 

 

인접행렬에서의 정렬 순서

인접 리스트의 value 값에 담기는 간선의 정보는 배열의 형태로 저장된다. 배열에 저장되는 간선들은 정렬의 순서가 표시되어 있지 않다. 다만 정점과 연결된 간선의 정보만 담게 된다.

인접 리스트에서 간선의 정렬 순서는 일반적으로 중요하지 않다. 하지만 우선순위를 고려한다면 간선들을 배열에 추가할 때 정렬 기준을 세워서 따로 정렬을 해줘야 한다. 

 

 

 

Graph 인접 리스트 구현하기

 

 

구현한 인접리스트는 무방향 그래프의 인접리스트다. 객체를 멤버 변수로 가지고 있고 총 6개의 메소드를 가진 클래스로 구현된다.

 

• addVertex(vertex) : 그래프에 새로운 Vertex를 추가한다.
• contains(vertex) : 그래프에 해당 Vertex가 존재하는지 확인한다.
• addEdge(fromVertex, toVertex) : fromVertex와 toVertex 사이의 간선을 추가한다.
• hasEdge(fromVertex, toVertex) : fromVertex와 toVertex 사이에 간선이 존재하는지 확인 후 Boolean 값 반환
• removeEdge(fromVertex, toVertex) : fromVertex와 toVertex 사이의 간선을 삭제한다.
• removeVertex(Vertex) : 그래프 상에서 정점을 삭제하고, 정점과 연결된 모든 간선을 삭제한다.

 

/*
	# 무방향 그래프 인접 리스트 구현
    # 작성자 : About-Tech
    # 날짜 : 2022-05-24
*/


class GraphWithAdjacencyList {
	constructor() {
		this.vertices = {};
	}

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

	contains(vertex) {
		// 인자로 넘겨받은 정점의 존재여부를 반환합니다.
		return Object.keys(this.vertices).includes(vertex) ? true : false;
	}

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

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

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

	hasEdge(fromVertex, toVertex) {
		if (!this.contains(fromVertex)) {
			return false;
		}
		return !!this.vertices[fromVertex].includes(toVertex);
	}

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

		if (this.hasEdge(fromVertex, toVertex)) {
			const index = this.vertices[fromVertex].indexOf(toVertex);
			this.vertices[fromVertex].splice(index, 1);
		}
    if (this.hasEdge(toVertex, fromVertex)) {
			const index = this.vertices[toVertex].indexOf(fromVertex);
			this.vertices[toVertex].splice(index, 1);
		}
	}

	removeVertex(vertex) {
		if (this.contains(vertex)) {
      
      while(this.vertices[vertex].length > 0){
        this.removeEdge(this.vertices[vertex][0], vertex);
      }
      delete this.vertices[vertex];      
		}
	}
}

 

 

[Algorithm] Javascript Graph Data Structure 그래프 자료구조 알고리즘