[JS] 그래프(Graph)

1. 그래프

 그래프란 연결되어있는 원소 간의 관계를 표현하는 자료구조를 말한다. 버스 노선도, 전철 노선도, 인간관계를 나타내는 연결구조는 구조가 너무나도 다양하고 복잡하기 때문에 선형 자료구조나 트리로 표현할 수 없다. 그래프는 연결할 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)로 구성된다. 그래프 G를 G = (V, E)로 정의하는데,  V는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선의 집합을 의미한다.

 

 

2. 그래프의 종류

 (1) 무방향 그래프

 

  무방향 그래프는 간선에 방향이 없는 그래프를 말한다. 무방향 그래프는 정점 V₁과 정점 V₂를 연결하는 간선을 (V₁, V₂) 로 표현한다.

 아래  [그림 1]은 무방향 그래프를 나타낸 그림이다.

 

[그림 1] 무방향 그래프

 

  위 무방향 그래프 G를 정점의 집합 V(G)와 간선의 집합 E(G)를 사용하여 다음과 같이 표현할 수 있다.

 

V(G) = {A, B, C, D} , E(G) = { (A,B), (A,D), (B,C), (B,D), (C,D) }

 

 

 (2) 방향 그래프

 

  방향 그래프는 간선에 방향이 있는 그래프를 말하며, 다이 그래프라고도 한다. 방향 그래프에서 정점 V₁에서 정점 V₂를 연결하는 간선

 V₁ → V₂를 <V₁, V₂>로 나타낸다. 여기서 V₁을 꼬리라고 부르고, V₂를 머리라고 한다. 또한 방향그래프에서 <V₁, V₂>, <V₂, V₁>은 서로   다른 간선이다. 아래 [그림 2]는 방향 그래프의 그림을 나타낸다.

 

[그림 2] 방향 그래프

 

  위 방향 그래프 G를 정점의 집합 V(G)와 간선의 집합 V(E)를 사용하여 다음과 같이 표현할 수 있다.

 

V(G) = {A, B, C}  E(G) = { <A,B>, <A,C>, <B,C>, <C,A> } 

 

 

 (3) 부분 그래프

 

  부분 그래프는 원래 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 말한다. 그래프 G와 부분그래프 G`는 종속적인 관계를   갖는다.

 

V(G`) ⊆ V(G),  E(G`) ⊆ E(G)

[그림 3] 그래프 G와 부분 그래프 G`

 

 

 (4) 가중 그래프

 

  가중 그래프는 간선에 가중치를 할당한 그래프를 말하며 네트워크라고도 부른다.

 

[그림 4] 가중 그래프

 

3. 관련 용어

 그래프에서 정점 V₁과 V₂가 연결되어 있는 간선 (V₁, V₂)가 있을 때, 두 정점 V₁, V₂는 인접되어 있다고 하고, 간선 (V₁, V₂)는 정점 V₁과  V₂에 부속되어 있다고 한다. [그림 1]을 보면,

 

[그림 1] 무방향 그래프

 

 정점 A와 인접한 정점은 B, C이고, 정점 A에 부속되어 있는 간선은 (A,B), (A,C)다. 또한 정점에 부속되어 있는 간선의 수를 차수라고 한다. 정점 A의 차수는 2이고, B의 차수는 3이다. 이번엔 방향 그래프를 보자.

 

[그림 2] 방향 그래프

 

 방향 그래프에서는 정점에 부속된 간선의 방향에 따라서 진입차수와 진출차수가 생기는데, 정점을 머리로 하는 간선의 수를 진입 차수라고 하고, 정점을 꼬리로 하는 간선의 수를 진출 차수라고 한다. 방향 그래프에서 정점의 차수는 진입차수와 진출차수를 합한 것과 같다. 위 그래프를 예로 들면 정점 B의 진입 차수는 1이고, 진출 차수도 1이 된다. 따라서 정점 B의 차수는 2가 된다.

 

 

 그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 것을 경로라고 한다. 경로를 구성하는 간선의 수를 경로 길이라고 한다. 위 방향 그래프로 예를 들어보자. 위 방향 그래프에서 우리는 정점 A에서 정점 C로 이동하려고 한다. 그를 위해 우리는 <A,B> <B,C>라는 두 개의 간선을 거쳐야한다. 이때 경로 길이는 2가 된다. 그런데, <A,C>라는 경로를 따라서 한번에 가는 경우도 있다. 이 경우에 경로의 길이는 1이 된다. <A,B>, <B,C>의 경로는 A → B → C의 정점을 이동한다. A, B, C는 서로 다른 정점이다. 이렇게 모두 서로 다른 정점으로 구성된 경로를 단순 경로라고한다. 하지만, A → B → D → C→ B → A 와 같은 경로는 단순 경로가 아니다. 그리고 단순 경로 중에서 A → B → D→ A와 같이 경로의 시작, 마지막 정점이 같은 경로를 사이클이라고 한다. 방향 그래프이면서 사이클이 없는 그래프를 DAG(Directed Acyclic Graph)라고 한다.

 

 

 그래프에서 두 정점 V₁에서 V₂까지의 경로가 있으면 정점 V₁와 V₂가 연결되었다고 한다. 서로 다른 쌍의 정점들 사이에 경로가 있는 그래프를 연결 그래프라고 한다. 하지만 연결되지 않은 정점이 있는 그래프를 단절 그래프(Disconnected Graph)라고 한다.

 

[그림 5] 연결 그래프와 단절 그래프

 

 

4. 구현

 그래프 구현 방식은 두 가지가 있다. 순차 자료구조 방식을 이용하는 2 차원 배열의 인접 행렬 방법(Adjacent Matrix)과 연결 자료 구조 방식인 연결리스트를 사용하는 인접리스트(Adjacent List) 방법이 있다.

 

 

 (1) 순차 자료구조 방식을 이용한 그래프의 구현

 

  그래프를 구성하는 정점에 대해서 간선의 유무를 저장하는 방법으로 정방행렬을 사용한다. n개의 정점을 가진 경우, n x n 정방 행렬을

 사용한다. 두 정점이 인접하면 1, 인접하지 않으면 0으로 표현한다. 그리고 머리, 꼬리가 같은 간선(자기 자신과 연결된 간선)은 없으므로   행렬 [n, n]의 값은 무조건 0이다.

 

[그림 6] 인접 행렬으로 표현

 

  무방향 그래프의 경우 방향성이 없기 때문에 간선[0][1]과 간선[1][0]의 값이 같아 대칭성을 이룬다. 하지만 방향 그래프의 경우 방향 값     이 있기 때문에 다른 값이 된다. 프로그램 코드로 구현하면 다음과 같다.

const Graph = function(n){
  this.graph = Array.from({length:n}, e => new Array(n).fill(0));
  
  // 간선 삽입 함수
  Graph.prototype.insertEdge = function (tail, head){
    const tailIdx = tail.charCodeAt(0) - 65;
    const headIdx= head.charCodeAt(0) -  65;

    // 삽입하려는 tail, head 정점이 같은 값을 때 에러
    if(tail === head){
      console.log("Error: The same values isn't inserted in Graph");
      return;
    }
    // 삽입하려는 간선이 없는 값일 때 에러
    if(tailIdx > n || headIdx > n){
      console.log("Error: IndexError, Confirm two parameter values again");
      return;
    }

    this.graph[tailIdx][headIdx] = 1;
  }

  // 매트릭스 출력 함수
  Graph.prototype.printMatrix = function(){
    const vertexs = Array.from({length:n}, (e,i) => String.fromCharCode(65+i));

    console.log(" ",...vertexs);

    for(let i=0; i<n; i++){
      const vertex = vertexs[i];
      const matrix = this.graph[i];
      console.log(`${vertex}`, ...matrix);
    }
  }
}


const main = (function() {
  const graph = new Graph(4);
  graph.insertEdge('A', 'B');
  graph.printMatrix();
})();

 

 

 (2) 연결 자료구조 방식을 이용한 그래프의 구현

 

  인접리스트로 그래프를 표현하는 방법은 각 정점에 대한 인접 정점들을 연결 리스트로 만드는 것이다. 리스트의 각 노드는 정점을 저장

 하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성한다. 어떤 정점의 연결 리스트는 그 정점에 인접한 정점의 수 만큼, 즉 그 정점

 의 차수만큼의 노드가 연결되어 있다. 리스트 내의 노드는 저장하는 정점에 대해서 오름차순으로 연결한다.

 

 

  그래서 나는 책의 방법을 인용하여 밑에 [그림 7]과 같이 n개의 배열을 만들어서 각 원소에 정점 'A'부터 'A'+n의 값을 가진 노드로 초기

 화 하려고한다. 만약 4의 입력값을 받는다면 배열안에는 [A값을 가진 노드, B값을 가진 노드, C값을 가진 노드, D값을 가진 노드]로 초기   화될 것이다.

 

[그림 7] 인접리스트 표현

  

  따라서 프로그램코드는 다음과 같다.

const GraphNode = function(data){
  this.vertex = data;
  this.link = null;
}


const Graph = function(n){
  this.graph = Array.from({length: n}, (e,i) => new GraphNode(String.fromCharCode(65+i)));

  Graph.prototype.insertEdge = function(tail, head){
    const findKey = tail.charCodeAt(0)-65;
    const newGraphNode = new GraphNode(head);

    if(tail === head){
      console.log("Error: the same values isn't inserted in graph");
    }

    if(findKey > n || findKey < 0){
      console.log("Key Error: Can't find the key you did input");
      return
    }

    let startNode = this.graph[findKey];

    while(startNode.link !== null){
      startNode = startNode.link;
    }
    startNode.link = newGraphNode;
  }

  Graph.prototype.printAdjList = function(){
    const printGraph = this.graph;
    const arrow = " → ";

    for(let i=0; i<n; i++){
      let printNode = printGraph[i];
      let str = printNode.vertex;

      while(printNode.link !== null){
        printNode = printNode.link;
        str += (arrow+printNode.vertex);
      }

      console.log(str);
    }
  }
}


const main = (function (){
  const graph = new Graph(4);
  graph.insertEdge('A', 'B');
  graph.insertEdge('A', 'C');
  graph.insertEdge('B', 'D');
  graph.insertEdge('D', 'C');
  graph.printAdjList();
}());

 

 

5. 참고 자료

자바로 배우는 쉬운 자료구조, 한빛 미디어