그래프

무지향성 그래프

간선간에 방향이 없는 그래프

 

간선과 정점 추가하기

//간선을 저장하기 위한 객체
function UndirectedGraph() {
    this.edges = {};
}
//정점(노드)
UndirectedGraph.prototype.addVertex = function(vertex) {
    this.edges[vertex] = {};
}
//가중치가 있는 간선을 추가하기 위해서는 this.edges 객체의 양쪽 정점을 사용해 가중치를 저장
UndirectedGraph.prototype.addEdge = function(vertex1, vertex2, weight) {
    if (weight == undefined) {
        weight = 0;
    }
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
}

ㄱㄱ

var graph1 = new UndirectedGraph();
graph1.addVertex(1);
graph1.addVertex(2);
graph1.addEdge(1, 2, 1);
graph1.edges; // 1: {2: 1},  2: {1: 1}
graph1.addVertex(3);
graph1.addVertex(4);
graph1.addVertex(5);
graph1.addEdge(2, 3, 8);
graph1.addEdge(3, 4, 10);
graph1.addEdge(4, 5, 100);
graph1.addEdge(1, 5, 88);

간선과 정점 삭제하기

UndirectedGraph.prototype.removeEdge = function(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];
    }
}


UndirectedGraph.prototype.removeVertex = function(vertex) {
    for (var adjacentVertex in this.edges[vertex]) {
        this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
}

ㄱㄱ

var graph2 = new UndirectedGraph();
graph2.addVertex(1);
graph2.addVertex(2);
graph2.addEdge(1, 2, 1);
graph2.edges; // 1: {2: 0},  2: {1: 0}
graph2.addVertex(3);
graph2.addVertex(4);
graph2.addVertex(5);
graph2.addEdge(2, 3, 8);
graph2.addEdge(3, 4, 10);
graph2.addEdge(4, 5, 100);
graph2.addEdge(1, 5, 88);
graph2.removeVertex(5);
graph2.removeVertex(1);
graph2.removeEdge(2, 3);

 

지향성 그래프

정점 간에 방향이 있는 그래프

 

간선과 정점 추가하기

function DirectedGraph() {
    this.edges = {};
}
DirectedGraph.prototype.addVertex = function(vertex) {
    this.edges[vertex] = {};
}
DirectedGraph.prototype.addEdge = function(origVertex, destVertex, weight) {
    if (weight === undefined) {
        weight = 0;
    }
    this.edges[origVertex][destVertex] = weight;
}

ㄱㄱ

var digraph1 = new DirectedGraph();
digraph1.addVertex("A");
digraph1.addVertex("B");
digraph1.addVertex("C");
digraph1.addEdge("A", "B", 1);
digraph1.addEdge("B", "C", 2);
digraph1.addEdge("C", "A", 3);

삭제

DirectedGraph.prototype.removeEdge = function(origVertex, destVertex) {
    if (this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) {
        delete this.edges[origVertex][destVertex];
    }
}

DirectedGraph.prototype.removeVertex = function(vertex) {
    for (var adjacentVertex in this.edges[vertex]) {
        this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
}

 

그래프 순회

너비 우선 검색BFS, breadth-first search

그래프에서 연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘

DirectedGraph.prototype.traverseBFS = function(vertex, fn) {
    var queue = [],
        visited = {};

    queue.push(vertex);

    while (queue.length) {
        vertex = queue.shift();
        if (!visited[vertex]) {
            visited[vertex] = true;
            fn(vertex);
            for (var adjacentVertex in this.edges[vertex]) {
                queue.push(adjacentVertex);
            }
        }
    }
}
digraph1.traverseBFS("B", (vertex) => {
    console.log(vertex)
});

시간 복잡도: O(V+E)   (V는 정점의 개수, E는 간선의 개수)

깊이 우선 검색DFS, depth-first search

그래프에서 다른 연결을 방문하기 전에 하나의 연결을 깊게 파고들며 순회하는 검색 알고리즘

DirectedGraph.prototype.traverseDFS = function(vertex, fn) {
    var visited = {};
    this._traverseDFS(vertex, visited, fn);
}

DirectedGraph.prototype._traverseDFS = function(vertex, visited, fn) {
    visited[vertex] = true;
    fn(vertex);
    for (var adjacentVertex in this.edges[vertex]) {
        if (!visited[adjacentVertex]) {
            this._traverseDFS(adjacentVertex, visited, fn);
        }
    }
}
digraph1.traverseDFS("B", (vertex) => {
  console.log(vertex);
});

시간 복잡도: O(V+E) v는 정점의 개수, e는 간선의 개수

가중치가 있는 그래프와 최단 경로

다익스트라의 알고리즘: 최단 경로

다익스트라의 알고리즘은 목적지에 도달하기 위해 각 단계에서 최단 경로를 취하는 방식으로 동작한다. 처음에는 일부 노드에 도달할 수 없을 수도 있기 때문에 거리를 무한으로 표기한다. 그러고 나서 각 순회 반복 루프 때마다 각 노드에 대한 최단 경로를 선택한다.

function _isEmpty(obj) {
    return Object.keys(obj).length === 0;
}

function _extractMin(Q, dist) {
    var minimumDistance = Infinity,
        nodeWithMinimumDistance = null;
    for (var node in Q) {
        if (dist[node] <= minimumDistance) {
            minimumDistance = dist[node];
            nodeWithMinimumDistance = node;
        }
    }
    return nodeWithMinimumDistance;
}

DirectedGraph.prototype.Dijkstra = function(source) {
    // create vertex set Q
    var Q = {},
        dist = {};
    for (var vertex in this.edges) {
        // unknown distances set to Infinity
        dist[vertex] = Infinity;
        // add v to Q
        Q[vertex] = this.edges[vertex];
    }
    // Distance from source to source init to 0
    dist[source] = 0;

    while (!_isEmpty(Q)) {
        var u = _extractMin(Q, dist); // get the min distance

        // remove u from Q
        delete Q[u];

        // for each neighbor, v, of u:
        // where v is still in Q.
        for (var neighbor in this.edges[u]) {
            // current distance
            var alt = dist[u] + this.edges[u][neighbor];
            // a shorter path has been found
            if (alt < dist[neighbor]) {
                dist[neighbor] = alt;
            }
        }
    }
    return dist;
}

var digraph1 = new DirectedGraph();
digraph1.addVertex("A");
digraph1.addVertex("B");
digraph1.addVertex("C");
digraph1.addVertex("D");
digraph1.addEdge("A", "B", 1);
digraph1.addEdge("B", "C", 1);
digraph1.addEdge("C", "A", 1);
digraph1.addEdge("A", "D", 1);
console.log(digraph1);
// DirectedGraph {
// V: 4,
// E: 4,
// edges: { A: { B: 1, D: 1 }, B: { C: 1 }, C: { A: 1 }, D: {} }}
digraph1.Dijkstra("A"); // { A: 0, B: 1, C: 2, D: 1 }

시간 복잡도: O(V^2+E)

위상 정렬

위상 정렬 알고리즘은 순서를 기록하기 위해 스택을 사용하는 수정된 버전의 깊이 우선 정렬이다.

간단히 이야기하면 위상 정렬 알고리즘의 동작 방식은 어떤 노드로부터 깊이 우선 정렬을 수행해 해당 노드와 연결된 모든 노드들을 재귀적으로 방문하면서 해당 노드들을 스택에 추가한다.

DirectedGraph.prototype.topologicalSortUtil = function(v, visited, stack) {
    visited.add(v);

    for (var item in this.edges[v]) {
        if (visited.has(item) == false) {
            this.topologicalSortUtil(item, visited, stack)
        }
    }
    stack.unshift(v);
};

DirectedGraph.prototype.topologicalSort = function() {
    var visited = new Set(),
        stack = [];


    for (var item in this.edges) {
        if (visited.has(item) == false) {
            this.topologicalSortUtil(item, visited, stack);
        }
    }
    return stack;
};

var g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addVertex('E');
g.addVertex('F');

g.addEdge('B', 'A');
g.addEdge('D', 'C');
g.addEdge('D', 'B');
g.addEdge('B', 'A');
g.addEdge('A', 'F');
g.addEdge('E', 'C');
var topologicalOrder = g.topologicalSort();
console.log(g);
// DirectedGraph {
// V: 6,
// E: 6,
// edges:
//  { A: { F: 0 },
//    B: { A: 0 },
//    C: {},
//    D: { C: 0, B: 0 },
//    E: { C: 0 },
//    F: {} } }
console.log(topologicalOrder); // [ 'E', 'D', 'C', 'B', 'A', 'F' ]

시간 복잡도: O(V+E)

공간 복잡도: O(V)

 

요약