Graph에 대한 이해 Javascript

문제

Graph 구현을 위한 기본적인 코드가 작성되어 있습니다. Graph 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해 주세요.

메소드

• addVertex(): 그래프에 버텍스를 추가해야 합니다.

• contains(vertex): 그래프에 해당 버텍스가 존재하는지 여부를 Boolean으로 반환해야 합니다.

• addEdge(from, to): fromVertex와 toVertext 사이의 간선을 추가합니다.

• hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.

• removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.

주의사항

• 인접 행렬 방식으로 구현해야 합니다.
• 구현해야 하는 그래프는 방향 그래프입니다.
• 구현해야 하는 그래프는 비가중치 그래프입니다.
• 구현해야 하는 그래프는 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다. (0, 1, 2, ... --> 정점)
• 인접 행렬 그래프는 정점이 자주 삭제되는 경우에는 적합하지 않기 때문에 정점을 지우는 메소드는 생략합니다.

예시

const adjMatrix = new GraphWithAdjacencyMatrix();
adjMatrix.addVertex();
adjMatrix.addVertex();
adjMatrix.addVertex();
console.log(adjMatrix.matrix);
/*
							TO
		 	  	 0  1  2
		  	0	[0, 0, 0],
	FROM 	1	[0, 0, 0],
		  	2	[0, 0, 0]
*/
let zeroExists = adjMatrix.contains(0);
console.log(zeroExists); // true
let oneExists = adjMatrix.contains(1);
console.log(oneExists); // true
let twoExists = adjMatrix.contains(2);
console.log(twoExists); // true

adjMatrix.addEdge(0, 1);
adjMatrix.addEdge(0, 2);
adjMatrix.addEdge(1, 2);

let zeroToOneEdgeExists = adjMatrix.hasEdge(0, 1);
console.log(zeroToOneEdgeExists); // true
let zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2);
console.log(zeroToTwoEdgeExists); // true
let oneToZeroEdgeExists = adjMatrix.hasEdge(1, 0);
console.log(oneToZeroEdgeExists); // false

console.log(adjMatrix.matrix);
/*
							TO
		 	  	 0  1  2
		  	0	[0, 1, 1],
	FROM 	1	[0, 0, 1],
		  	2	[0, 0, 0]
*/

adjMatrix.removeEdge(1, 2);
adjMatrix.removeEdge(0, 2);
let oneToTwoEdgeExists = adjMatrix.hasEdge(1, 2);
console.log(oneToTwoEdgeExists); // false
zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2);
console.log(zeroToTwoEdgeExists); // false

console.log(adjMatrix.matrix);
/*
							TO
		 	  	 0  1  2
		  	0	[0, 1, 0],
	FROM 	1	[0, 0, 0],
		  	2	[0, 0, 0]
*/

풀이

class Graph{
	constructor() {
    	this.matrix = [];
    }
    
    addVertex() {
    	for(let i = 0; i < this.matrix.length; i++){
        	this.matrix[i].push(0);
        }
        this.matrix.push(new Array(this.matrix.length + 1).fill(0));
    }
    
    contains(vertex){
    	return !!this.matrix[vertex];
    }
    
    addEdge(from, to){
    	if(from === undefined || to === undefined){
        	console.log("2개의 인자가 있어야 합니다.");
            return;
        }
        
        // 간선을 추가할 수 없는 상황
        if(from + 1 > this.matrix.length || to + 1 > this.matrix.length || from < 0 || to < 0){
        	console.log("매트릭스 범위 밖에 있습니다.");
            return;
        }
        this.matrix[from][to] = 1;
    }
    
    hasEdge(from, to){
    	return !!this.matrix[from][to];
    }
    
    removeEdge(from, to){
    	if(from === undefined || to === undefined){
        	console.log("2개의 인자가 필요합니다.");
            return;
        }
        // 간선을 지울 수 없는 상황에서는 지울 수 없다.
        if(from + 1 > this.matrix.length || to + 1 > this.matrix.length || from < 0 || to < 0){
        	return;
        }
        return this.matrix[from][to] = 0;
    }
}

우선 !! 느낌표 2개는 [undefined, "", 0] 인 경우 false를 반환하고 그 외 모든 결과는 true를 반환합니다.

그래프란?
node(=== vertex)와 그 node들 간의 간선(edge)를 하나로 모아 놓은 자료구조입니다.

그래프의 특징
꼭 모든 node들이 서로 관계를 갖고 있어야만 하지 않습니다. 따라서 그래프는 node간 연결이 없는 고립된 부분이 있을 수도 있고, 순환할 수도 있고, 안할수도 있기 때문에 형식에 얽매이지 않은 자료구조라고 볼 수 있습니다. 이러한 특성 때문에 그래프 자료구조를 네트워크 모델이라고 부릅니다.

그래프 자료구조 용어
node(vertex): 위치라는 개념입니다.
edge(간선): 위치 간의 관계, 즉 노드를 연결하는 선을 말합니다. (link, branch라고 부르기도 합니다.)