- adjacency list를 사용하는 경우: 모든 경로를 구할 때!
class GraphWithAdjacencyList {
constructor() {
this.vertices = {};
}
addVertex(vertex) {
if (this.vertices[vertex]) return;
this.vertices[vertex] = [];
}
contains(vertex) {
return this.vertices[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) {
this.removeEdge(this.vertices[vertex][0], vertex);
}
delete this.vertices[vertex];
}
}
}