그래프에 대한 이해

그래프 용어

정점: 그래프를 형성하는 노드
간선: 그래프에서 노드 간의 연결을 말한다.
정점 차수: 정점(노드)에 연결된 간선의 개수를 나타낸다.
희소 그래프: 정점들 간에 가능한 연결 중 일부만 존재하는 경우 해당 그래프를 희소 그래프라고 한다.
밀집 그래프: 다양한 정점들 간에 연결이 많은 경우 해당 그래프를 밀집 그래프라고 한다.
순환 그래프: 어떤 정점에서 출발해 해당 정점으로 다시 돌아오는 경로가 존재하는 지향성 그래프를 말한다.
가중치: 간선에 대한 값으로, 문맥에 따라 다양한 것을 나타낼 수 있다.

 

// 무지향성 그래프
function UndirectedGraph (){
  this.edges = {};
}

UndirectedGraph.prototype.addVertex = function (vertex) {
  this.edges[vertex] = {};
}

UndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) {
  if (weight == undefined) {
    weight = 0;
  }
  this.edges[vertex1][vertex2] = weight;
  this.edges[vertex2][vertex1] = weight;
}

const graph1 = new UndirectedGraph();
graph1.addVertex(1);
graph1.addVertex(2);
graph1.addEdge(1,2,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);

//console.log(graph1)

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 (let adjacentVertex in this.edges[vertex]) {
    this.removeEdge(adjacentVertex, vertex)
  }
  
  delete this.edges[vertex];
}

const graph2 = new UndirectedGraph();
graph2.addVertex(1);
graph2.addVertex(2);
graph2.addEdge(1,2,1);
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);

// console.log(graph2)

// 지향성 그래프
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
}

let 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);

// console.log(digraph1)

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 (let adjacentVertex in this.edges[vertex]) {
    this.removeEdge(adjacentVertex, vertex)
  }
  delete this.edges[vertex];
}

그래프 순회

1. 너비 우선 검색

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

트리 자료 구조에 대한 차수 우선 순회와 마찬가지로 너비 우선 검색은 큐를 필요로 한다. 각 노드에 연결된 각 정점을 큐에 추가한 다음 큐의 각 항목을 방문한다.

 

DirectedGraph.prototype.traverseBFS = function (vertex, fn) {
  let queue = [],
      visited = {};
  
  queue.push(vertex);
  
  while (queue.length) {
    vertex = queue.shift();
    if (!visited[vertex]) {
      visited[vertex] = true;
      fn(vertex);
      for (let adjacentVertex in this.edges[vertex]) {
        queue.push(adjacentVertex);
      }
    }
  }
}

digraph1.traverseBFS("B", (vertex) =>{console.log(vertex)})

 

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

너비 우선 검색의 경우 시간 복잡도는 O(V+E)이다. 여기서 V의 개수는 정점의 개수이고, E는 간선의 개수다. 전체 그래프를 순회하기 위해서는 알고리즘이 모든 간선과 노드를 방문해야 하기 때문이다.

2. 깊이 우선 검색

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

 

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

DirectedGraph.prototype._traverseDFS = function (vertex, visited, fn) {
  visited[vertex] = true;
  fn(vertex);
  for (let adjacentVertex in this.edges[vertex]) {
    if (!visited[adjacentVertex]){
      this._traverseDFS(adjacentVertex, visited, fn);
    }
  }
}

 

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

깊이 우선 검색의 경우 시간 복잡도는 O(V+E)이다. 이 경우 역시 전체 그래프를 순회하기 위해서는 알고리즘이 모든 간선과 노드를 방문해야 한다.

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

가중치가 있는 간선을 지닌 그래프

그래프의 간선이 정점 간에 연결을 나타낸다는 점을 기억하자. 간선이 연결을 형성한다면 가중치를 해당 연결에 할당할 수 있다.

가중치가 있는 간선 그래프에 있어 가장 중요한 질문은 어떤 노드에서 다른 노드까지의 가장 짧은 경로가 무엇인지다. 그래프의 최단 경로 알고리즘에는 여러 종류가 있는데, 그 중 이 포스트에서 다룰 내용은 다익스트라의 알고리즘이다.

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

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

 

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

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

DirectedGraph.prototype.Dijkstra = function(source) {
  // 정점 집합 Q를 생성한다.
  let Q = {}, dist = {};
  for (let vertex in this.edges){
    dist[vertex] = Infinity;
    Q[vertex] = this.edges[vertex];
  }
  
  dist[source] = 0;
  
  while (!_isEmpty(Q)) {
    let u = _extractMin(Q, dist)
    
    delete Q[u]
    
    for (let neighbor in this._edges[u]) {
      let alt = dist[u] + this.edges[u][neighbor];
      
      if (alt < dist[neighbor]) {
        dist[neighbor] = alt;
      }
    }
  }
  return dist
}

 

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

위 알고리즘은 너비 우선 검색 알고리즘과 비슷하다. 하지만 시간 복잡도 O(n)인 _ extractMin 메소드를 필요로 한다. 이로 인해 위 알고리즘의 시간 복잡도는 O(V^2+E)이다.

위상 정렬

지향성 그래프의 경우 다양한 적용 사례에 있어 어떤 노드를 가장 먼저 처리해야 할지 알아야 한다. 이러한 예로 작업 스케쥴러가 있다. 작업 스케쥴러에서는 한 작업이 이전 작업이 수행됐는지 여부에 의존도를 지닌다. 또 다른 예로 자바스크립트 의존도 매니저의 경우 어떤 라이브러리 가져오기를 수행할 때 해당 라이브러리 이전에 가져와야 할 라이브러리가 무엇인지 알아야 한다. 위상 정렬 알고리즘은 이러한 기능을 수행한다. 위상 정렬 알고리즘은 순서를 기록하기 위해 스택을 사용하는 수정된 버전의 깊이 우선 정렬이다.

 

DirectedGraph.prototype.topologicalSortUtil = function (v, visited, stack) {
  visited.add(v);
  
  for (let item in this.edges[v]){
    if (visited.has(item) === false){
      this.topologicalSortUtil(item, visited, stack)
    }
  }
  stack.unshift(v);
}

DirectedGraph.prototype.topologicalSort = function () {
  let visited = new Set(),
      stack = [];
  
  for(let item in this.edges) {
    if (visited.has(item) === false) {
      this.topologicalSortUtil(item, visited, stack);
    }
  } 
  return stack;
}

 

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

위상 정렬 알고리즘은 단순히 추가적인 스택을 지닌 깊이 웃건 정렬이다. 따라서 위상 정렬 알고리즘의 시간 복잡도는 깊이 우선 정렬과 동일하다.