그래프
무지향성 그래프
class UndirectedGraph {
constructor() {
this.edges = {};
}
addVertex(vertex) {
this.edges[vertex] = {};
}
addEdge(vertex1, vertex2, weight = 0) {
if (this.edges[vertex1] && this.edges[vertex2]) {
this.edges[vertex1][vertex2] = weight;
this.edges[vertex2][vertex1] = weight;
}
}
removeEdge(vertex1, vertex2) {
if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
delete this.edges[vertex1][vertex2];
}
if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
delete this.edges[vertex2][vertex1];
}
}
removeVertex(vertex) {
for (const adjacentVertex in this.edges[vertex]) {
this.removeEdge(adjacentVertex, vertex);
}
delete this.edges[vertex];
}
}
지향성 그래프
class DirectedGraph {
constructor() {
this.edges = {};
}
addVertex(vertex) {
this.edges[vertex] = {};
}
addAdge(orignVertex, destVertex, weight = 0) {
this.edges[orignVertex][destVertex] = weight;
}
removeEdge(orignVertex, destVertex) {
if (
this.edges[orignVertex] &&
this.edges[orignVertex][destVertex] !== undefined
) {
delete this.edges[orignVertex][destVertex];
}
}
removeVertex(vertex) {
for (const adjacentVertex in this.edges) {
this.removeEdge(adjacentVertex, vertex);
}
delete this.edges[vertex];
}
// 너비 우선 검색
traverseBFS(vertex, fn) {
const queue = [vertex];
const visited = {};
while (queue.length > 0) {
const cur = queue.shift();
if (!visited[cur]) {
visited[cur] = true;
fn(cur);
for (const adjacentVertex in this.edges[cur]) {
queue.push(adjacentVertex);
}
}
}
}
// 깊이 우선 검색
traverseDFS(vertex, fn, visited = {}) {
visited[vertex] = true;
fn(vertex);
for (const adjacentVertex in this.edges[vertex]) {
if (!visited[adjacentVertex]) {
this.traverseDFS(adjacentVertex, visited, fn);
}
}
}
// 가중치가 있을 때 최단 경로
dijkstra(source) {
const notVisited = {};
const dist = {};
const isEmpty = () => {
return Object.keys(notVisited).length === 0;
};
const extractMin = () => {
let minimumDist = Infinity;
let nodeWithMinimumDist = null;
for (const node in notVisited) {
if (dist[node] <= minimumDist) {
minimumDist = dist[node];
nodeWithMinimumDist = node;
}
}
return nodeWithMinimumDist;
};
for (const vertex in this.edges) {
dist[vertex] = Infinity;
notVisited[vertex] = true;
}
dist[source] = 0;
while (!isEmpty()) {
const u = extractMin();
delete notVisited[u];
for (const neighbor in this.edges[u]) {
const alt = dist[u] + this.edges[u][neighbor];
if (alt < dist[neighbor]) dist[neighbor] = alt;
}
}
return dist;
}
// 위상 정렬
topologicalSort() {
const visited = {};
const stack = [];
const topologicalSortUtil = (vertex) => {
visited[vertex] = true;
for (const item in this.edges[vertex]) {
if (!visited[item]) {
topologicalSortUtil(item, visited, stack);
}
}
stack.unshift(vertex);
};
for (const item in this.edges) {
if (!visited[item]) {
topologicalSortUtil(item, visited, stack);
}
}
return stack;
}
}