[Data-Structure] Graph (그래프)

오늘은 비선형 구조 중 하나인 그래프(Graph)에 대해서 공부했다.

그래프(Graph)는 노드(Node, 또는 정점 -vertex- 이라고도 부른다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성된다. 그래프는 무방향(undirected)일 수도 있으며, 이는 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미이다. 한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미한다.

그래프(Graph) 예시

• 진입 차수, 진출 차수란? 
  • 진입 차수 : 외부노드에서 해당 노드로 들어오는 간선의 수
  • 진출 차수 : 해당 노드에서 외부로 향하는 간선의 수
• 그래프 구현 방식 중 인접 행렬 방식과 인접 리스트 방식의 차이
  • 인접 행렬 방식 : 그래프의 연결 관계를 이차원 배열로 나타내어 graph[i, j] 일 때 i와 j 사이의 관계가 있다면 1, 없다면 0으로 나타낸다.
  • 인접 리스트 방식 : 그래프의 연결 관계를 배열로 나타내는 방식이다. graph{i : [j], j : [i]} 일 때 i와 j 사이의 관계가 있음을 나타낸다.  
• 앞서 봤던 트리(Tree)는 그래프의 한 종류로 트리와 그래프의 차이를 알아보자면 트리는 루트 노드가 존재하며 사이클을 이룰 수 없지만 그래프는 루트 노드가 존재하지 않고 사이클이 가능하다는 차이점이 있다. (하나의 노드를 여러 노드와 동시에 연결이 가능하다. )

Js 코드를 이용해서 인접 리스트 방식으로 구현을 해보았다.

/* Undirected Graph */
class Graph {
  constructor() {
    /*
     *  ex)
     *    nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     */
    this.nodes = {};
  }

  // 그래프에 노드를 추가
  addNode(node) {
    this.nodes[node] = this.nodes[node] || []; // node 키에 해당하는 값(배열)이 있다면 그 값을 넣어주고 없으면 빈 배열
  }
  
  // 그래프에 해당 노드가 존재하는지 여부를 반환
  contains(node) {
    if(this.nodes.hasOwnProperty(node)){ // this.nodes 객체에 node 키가 있는지 체크
      return true;
    }
   return false;
  }

  // 그래프에서 노드를 삭제
  removeNode(node) {
    for(let el of this.nodes[node]){
        this.removeEdge(node, el); // this.nodes[node]에 해당하는 배열의 모든 요소와 연결 관계를 삭제
      }
      delete this.nodes[node]; // 전체 노드에서 없애주기
  }

  // fromNode와 toNode 사이의 간선 존재 여부를 반환
  hasEdge(fromNode, toNode) {
    if( this.nodes[fromNode] !== undefined && this.nodes[fromNode].includes(toNode) === true ){ // 객체의 키값에 해당하는 배열안에서 찾을 노드가 존재하는지 확인
      return true;
    }
    return false;
  }
  
  // fromNode와 toNode 사이의 간선을 추가
  addEdge(fromNode, toNode) { // 각 노드에 해당하는 배열에 연결할 노드 값 추가
    this.nodes[fromNode].push(toNode); 
    this.nodes[toNode].push(fromNode); 
  }

  // // fromNode와 toNode 사이의 간선을 삭제
  removeEdge(fromNode, toNode) { // 각 노드에 해당하는 키를 찾아 요소 제거
    this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1)
    this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1)
  }
}

 

사용 예시이다.

let graph = new Graph();

graph.addNode(4);
graph.addNode(5);
console.log(graph.contains(5)); // true

graph.addEdge(5, 4);
console.log(graph.hasEdge(4, 5)); //true

graph.removeNode(5);
console.log(graph.contains(5)); // false
console.log(graph.hasEdge(4, 5); // false

 

그래프의 종류에는 여러가지가 있지만 오늘은 무방향 그래프만 공부해보았다.

 

그래프의 종류

• 무방향 그래프
  • 방향성이 없는 그래프로 위에 구현한 예시도 무방향 그래프이다. (간선으로 연결이 되어 있으면 양방향으로 통행이 가능하다.)
• 방향 그래프
  • 방향성이 있는 그래프로 간선에 화살표로 방향을 표시한다. 정해진 방향대로만 이동이 가능하다.

정해진 화살표 방향으로만 이동이 가능

• 가중치 그래프
  • 간선에 가중치가 있어 두 정점을 이동하는데 드는 비용이 적용된다.

간선을 이동하는데 드는 비용 예시

• 사이클 구조 그래프
  •  그래프의 시작 정점과 종료 정점이 같은 경우 (고리 구조)

정점A에서 출발하여 다시 정점A로 돌아온다.

• 비순환 구조 그래프
  •  순환 구조와는 반대로 순환하지 않는 그래프이다.
• 완전 그래프
  •  모든 정점이 서로 연결되어 있는 그래프이다.

모든 정점이 간선으로 연결되어 있다.