ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Data Structure - Graph(그래프)
    Programming/Data Structure(자료 구조) 2019. 4. 7. 18:17

    - Graph(그래프) -

    • Graph(그래프)의 정의
      - 노드(node)와 그 노드의 연결선인 엣지(edge)를 모아 놓은 자료 구조
      - 연결되어 있는 객체간의 관계를 표현하기 위한 자료 구조
      - 계층 관계인 트리와는 다르게 네트워크 관계이다
    • Graph(그래프)와 Tree(트리)의 차이

     

    • Graph(그래프)의 특징
      - 네트워크 모델이다
      - 2개 이상의 경로가 가능하다
      - 트리처럼 root라는 개념이 없다
      - 부모 - 자식 관계가 없다
    • Graph(그래프)의 탐색 방법
      1. DFS(깊이 우선 탐색)
       - 그래프의 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중 아직 방문하지 않은 정점 u를 선택한다.
       - 만약 그러한 정점이 없다면 탐색은 종료한다
       - 만약 아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다.

       2. BFS(너비 우선 탐색)

        - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하        는 순회 방법

     

    • Pseudo - Code(의사 코드)
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      // Graph(그래프)를 구현하기 위한 의사 코드
      // 노드와 엣지를 추가하고 삭제하는 메소드와
      // 탐색하는 메소드를 가지고있다
       
      const Graph = function() {
      1. 생성자
      2. value라는 키를 갖고 그안에 edge라는 키를 갖는다 -> 객체 안에 객체인 형태
      };
       
      Graph.prototype.addNode = function(node) {
      1. 새로운 노드를 추가하는 메소드
      };
       
      Graph.prototype.contains = function(node) {
      1. 노드를 순회하여 해당 노드가 있는지 탐색하는 메소드
      2. if문을 사용하여 작성
      };
       
      Graph.prototype.removeNode = function(node) {
      1. 해당 노드를 삭제하는 메소드
      2. 해당 노드가 삭제되면 연결된 edge도 삭제하도록 구현
      };
       
      Graph.prototype.hasEdge = function(fromNode, toNode) {
      1. edge가 있는지 탐색하는 메소드
      2. 두 노드가 연결되어 있는지를 탐색
      };
       
      Graph.prototype.addEdge = function(fromNode, toNode) {
      1. edge를 추가하는 메소드
      2. from과 to 노드에 각각 엣지가 동일하게 추가되어야한다
      };
       
      Graph.prototype.removeEdge = function(fromNode, toNode) {
      1. edge를 삭제하는 메소드
      2. 연결된 노드간의 edge를 다 삭제해야한다
      };
       
      Graph.prototype.forEachNode = function(cb) {
      1. callback함수의 형태로 작성
      2. 노드를 순회하며 각 노드의 값을 함수에 넣는 메소드
      };
      <------------------------------------------------------------------------->
      //실제 코드 구현
      const Graph = function() {
          this.value = {};
          this.value.edge = {};
      };
       
      Graph.prototype.addNode = function(node) {
          this.value[node] = node;
      };
       
      Graph.prototype.contains = function(node) {
          if(this.value[node] === node){
              return true;
          } else{
              return false;
          }
      };
       
      Graph.prototype.removeNode = function(node) {
          this.value[node] = undefined;
          if(this.value.edge.hasOwnProperty(node)){
              this.removeEdge(node, node);
          }
          for(let key in this.value.edge){
              if(this.value.edge[key] === node){
                  this.removeEdge(null, key);
              }
          }
      };
       
      Graph.prototype.hasEdge = function(fromNode, toNode) {
          if(this.value.edge[fromNode] === toNode){
              return true;
          } else if(this.value.edge[toNode] === fromNode){
              return true;
          } else{
              return false;
          }
      };
       
      Graph.prototype.addEdge = function(fromNode, toNode) {
          this.value.edge[fromNode] = toNode;
          this.value.edge[toNode] = fromNode;
      };
       
      Graph.prototype.removeEdge = function(fromNode, toNode) {
          this.value.edge[fromNode] = undefined;
          this.value.edge[toNode] = undefined;
      };
       
      Graph.prototype.forEachNode = function(cb) {
          for(var key in this.value){
              if(typeof this.value[key] === 'number'){
                  cb(this.value[key]);
              }
          }
      };
       
      cs
Designed by Tistory.