[Algorithm] Javascript Graph 자료구조 인접행렬(Adjacency Matrix) 구현하기

How to implement Graph Data Structure in Javascript?

 

 

Graph 인접행렬 구현하기

 

그래프(Grpah) 자료구조는 노드를 간선으로 연결해 관계를 표현할 수 있는 자료구조다. 네비게이션에서 최단거리를 구하는 알고리즘을 구현할 때 그래프 자료구조를 사용한다. 정점(Vertex)와 간선(Edge)로 구성된다.

 

그래프 자료구조는 크게 방향성 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분된다. 또한 그래프 자료구조는 모든 정점을 순회하기 때문에 루트 노드, 부모 노드, 자식 노드의 개념이 없다.

 

 

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

 

Graph 소스코드 구현

 

Javascript에서 그래프를 구현하기 위해서는 Class를 생성한다. 멤버변수로는 인접행렬인 matrix를 가지고 5개의 메소드를 가진다.

 

아래에서 구현하는 그래프는 방향성 그래프이자 비가중치 그래프다. 또한 모든 정점이 연결된 완전 그래프다. 정점간 간선이 연결되어 있고, 방향성이 정해져 있기 때문에 인접행렬로 간단하게 표현할 수 있다.

 

 

• addVertex() : 그래프에 새로운 정점(Vertex)를 추가한다.
• contains() : 그래프 상에 해당 정점(Vertex)가 존재하는지 확인한다.
• addEdge() : from과 to 사이에 새로운 간선을 추가한다.
• hasEdge() : from과 to 사이에 간선이 존재하는지 확인한다.
• removeEdge() : from과 to 사이에 존재하는 간선을 삭제한다.

 

class GraphWithAdjacencyMatrix {
	constructor() {
		this.matrix = [];
	}

	addVertex() {
		const currentLength = this.matrix.length;
		for (let i = 0; i < currentLength; i++) {
			this.matrix[i].push(0);
		}
		this.matrix.push(new Array(currentLength + 1).fill(0));
	}

	contains(vertex) {
        return vertex <= this.matrix.length;
	}

	addEdge(from, to) {
		const currentLength = this.matrix.length -1 ;
		if (from === undefined || to === undefined) {
			console.log("2개의 인자가 있어야 합니다.");
			return;
		}
		if (from > currentLength || to > currentLength || from < 0 || to < 0) {
			console.log("범위가 매트릭스 밖에 있습니다.");
			return;
		}
        this.matrix[from][to] = 1;
	}

	hasEdge(from, to) {
    return this.matrix[from][to] === 1;
	}

	removeEdge(from, to) {
		const currentLength = this.matrix.length -1 ;
		if (from === undefined || to === undefined) {
			console.log("2개의 인자가 있어야 합니다.");
			return;
		}
		if (from > currentLength || to > currentLength || from < 0 || to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
		}
        this.matrix[from][to] = 0;
	}
}

 

 

위 소스코드를 인접행렬로 표현하면 다음과 같다.

 

 

 

[Algorithm] Javascript Tree 자료구조 구현하기 (소스코드 포함)