[자료구조/알고리즘]Graph

자료구조 Graph에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다.

코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다.

1. Graph

Graph 란

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.
• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다
• 간접적인 관계가 있는 경우 몇 개의 점과 전에 걸쳐 이어진다.
• 하나의 점 : 정점 vertex라고 표현
• 하나의 선 : 간선 edge라고 표현

Graph의 종류

• 무방향 그래프(Undirected Graph) 연결 완계에서 방향성이 없는 그래프를 말한다.
• 방향 그래프(Directed Graph) 간선에 방향 정보가 포함되어있는 그래프. digraph라고도 부른다.
• 완전 그래프(Complete Graph)
  • 무방향, 방향 그래프는 간선의 연결 형태에 따라서 완전 그래프로 구분이 된다.
  • 완전 그래프란 다른 모든 정점을 연결한 그래프를 말한다.
  • 무방향 그래프에서 최대 간선의 수 : n(n-1)/2
  • 방향 그래프에서 최대 간선의 수 : n(n-2)
  
• 가중치 그래프(Weight Graph)
  • 정점간의 유무뿐만 아니라 가중치가 추가됨
  • 연결의 강도가 얼마나 되는지에 대한 정보가 추가된다
• 비가중 그래프 (Unweight Graph)
  • 정점 간의 연결 유무만을 판단
  • 가중치(연결의 강도) 모름
  
  그림출처

• 부분 그래프

원 그래프의 일부 장점 및 간선으로 이루어진 그래프를 뜻함

그림출처

알아두어야 할 Graph 용어들

• 진입 칩 수 (in-dgree) / 진출 치수 (out-degree) : 한 정점에 진입하고 진출하는 간선이 몇 개인지 나타낸다.
• 인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 두 정점은 인접한 정점이다.
• 자기 루프 (self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 "자기 루프를 가졌다"라고 표현한다.
• 사이클(Cycle) 한 정점에서 시작하여 다시 해당 정점으로 돌아올 수 있으면 "사이클이 있다고 표현한다.

Graph의 집합표현

그래프는 정점과 간섭의 집합이다. 이에 따라 집합의 표기법을 사용하여 표현할 수 있다.

1. 무방향 그래프의 집합 표현
   1. 그래프 G의 정점 집합: V(G)로 표기 , 여기서 G = graph V(G)={A, B, C, D}
   2. 그래프 G의 간선 집합: E(G)로 표기, 정점 A와 정점 B를 연결하는 간선은 (A, B)로 표시한다. 무방향 그래프에서 (A, B)와 (B, A)는 같은 간선을 나타낸다. E(G) = {(A, B), (A, C), (A, D), (B, C), (C, D)}
2. 방향 그래프의 집합 표현
   1. 그래프 G의 정점 집합 V(G) ={A, B, C, D}
   2. 그래프 G의 간선 집합 E(G) = {<A, B>, <A, C>, <D, A>) <A, B>는 A가 정점 C를 가리키는 간선을 나타낸다

Graph의 ADT

• matrix : 배열로 선언된 Graph 자체
• addVertex() : 정점을 추가한다.
• addEdge(from , to) : 매개변수 from과 to로 전달된 정점을 연결하는 간선을 그래프에 추가하다.
• contains(vertex) : 정점이 있는지 확인한다.
• hasEdge(from, to) : from에서 to로 간선이 있는지 확인한다.
• removeEdge(from, to) : from에서 to로 가는 간선을 삭제한다.

Graph의 시간 복잡도 (Big-O)

• 데이터 삽입 : 뒤에 데이터를 삽입하므로 시간 복잡도는 O(1)이다.
• 데이터 삭제 : 맨 앞의 자료를 삭제하므로 시잔 복잡도는 O(1)이다.
• 데이터 탐색 : 맨 앞의 요소부터 맨 마지막까지 검색을 해야 하므로 시간 복잡도는 O(n)이다.

Graph의 두 가지 구현 방법

1. 인접 행렬 (Adjacent matrix) 기반 그래프 :

• 인접 행렬은 두 정점 사이에 관계가 있는지 없는지 확인하기에 용이하다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.
• 무방향 그래프 : 정방 행렬을 활용
  • 정점의 길이만큼의 정방 행렬을 활용한다. 두 정점이 연결되어있으면 1, 연결되어있지 않으면 0을 할당한다.
  • [n][m]=1 이면 [m][n]도 1이어야 하므로 대각선을 기준으로 대칭이다.

그림출처

2. 인접 리스트 (Adjacent list) 기반 그래프 : 연결 리스트 활용 —> 나중에 연결 리스트를 학습하고 추가로 학습하자.
   • 각 정점이 어떤 정점과 인접한 지를 리스트의 형태로 표현한다.
   • 각 정점마다 하나의 리스트를 갖고 있다.
   • 리스트는 자신과 인접한 다른 정점을 담고 있다.
   • 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
     • 인접 행렬은 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.
   
3. 그림 출처

Graph의 구현

• Class를 이용한 구현

  class GraphWithAdjacencyMatrix {
    constructor() {
      this.matrix = [];
    }

    addVertex() {
      // 인접 행렬 그래프 이므로 정점이 추가될 떄마다 대칭적으로 추가되어야 한다.
      // 만약 3x3의 행렬이 있는데, 정점을 한 개 추가하고 싶다면
      // matrix[0]~matrix[3] 까자 반복을 하면서  push(0)을 해주어 마지막에 요소를 추가해준다
      // matrix[4][0]~matrix[4][4] 0으로 채운 배열을 추가한다.

      const currentLength = this.matrix.length;
      for (let vertax of this.matrix) vertax.push(0);
      this.matrix.push(new Array(currentLength + 1).fill(0));
    }

    addEdge(from, to) {
      const currentLength = this.matrix.length;
            // 예외처리 함수가 true 이면 추가한다.
      return this.exceptionEdge(from, to, currentLength)
        ? (this.matrix[from][to] = 1)
        : false;
    }

    contains(vertax) {
      // vertax가 있는지 확인합니다
      return this.matrix[vertax] ? true : false;
    }

    hasEdge(from, to) {

      const currentLength = this.matrix.length;

      if (!this.exceptionEdge(from, to, currentLength)) return false;
      return this.matrix[from][to] ? true : false;
    }

    removeEdge(from, to) {
      // 간선을 삭제하고 삭제한다.
      const currentLength = this.matrix.length;
      // 예외처리를 한다
      return this.exceptionEdge(from, to, currentLength)
        ? (this.matrix[from][to] = 0)
        : false;
    }
    exceptionEdge(from, to, currentLength) {
      // 간선에 대한 예외 처리
      // 간선을 추가하려면 from , to 정점이 존재 해야한다
      // 입력된 from과 to의 길이가 범위 안에 있어야 한다 (matrix.length>from,to && from,to >0)
      if (from === undefined || to === undefined) {
        console.log("from' or 'to' is undefined");
        return false;
      }
      if (
        from > currentLength - 1 ||
        to > currentLength - 1 ||
        from < 0 ||
        to < 0
      ) {
        console.log("Input is out of range");
        return false;
      }
      return true;
    }
  }

  // create new graph
  const myMatrix = new GraphWithAdjacencyMatrix();
  // add 3 of vertax
  console.log("---addVertax test---");
  myMatrix.addVertex();
  myMatrix.addVertex();
  myMatrix.addVertex();
  console.log(myMatrix);

  console.log("---addEdge test---");
  myMatrix.addEdge(0, 1);
  myMatrix.addEdge(2, 3);
  myMatrix.addEdge(2, 3);
  myMatrix.addEdge(0, 2);
  console.log(myMatrix);

  console.log("---contain test---");
  console.log(myMatrix.contains(0));
  console.log(myMatrix.contains(3));
  console.log(myMatrix.contains(2));

  console.log("---hasEdge test---");
  console.log(myMatrix.hasEdge(0, 1));
  console.log(myMatrix.hasEdge(0, 2));
  console.log(myMatrix.hasEdge(2, 3));

  console.log("---removeEdge test---");
  myMatrix.removeEdge(0, 1);
  myMatrix.removeEdge(3, 1);
  myMatrix.removeEdge(1, 1);
  console.log(myMatrix);

/* 결과
---addVertax test---
GraphWithAdjacencyMatrix {
  matrix: [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
}
---addEdge test---
Input is out of range
Input is out of range
GraphWithAdjacencyMatrix {
  matrix: [ [ 0, 1, 1 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
}
---contain test---
true
false
true
---hasEdge test---
true
true
Input is out of range
false
---removeEdge test---
*/