그래프(Graph) 자료구조

• 이전에 살펴본 트리는 그래프의 일종이다. 그래프는 트리를 포괄하는 개념이다.
• 그래프를 코딩하는 방법은 여러 가지가 있으나, 인접 리스트(Adjacency List) 를 사용하여 그래프를 만들어본다.
• 그래프는 유한한(가변적인) 꼭지점(노드)들의 집합으로 구성된 데이터 구조다. 이 꼭지점들의 집합에 순서가 없는 경우에는 무방향 그래프(Undirected graph) 이고, 순서가 있는 경우에는 방향 그래프(Directed graph)라고 한다.
• 즉, 그래프는 노드와 노드들의 연결을 모은 것이다. 아래와 같은 이미지도 유효한 그래프다. 트리와 달리 부모 노드 같은 것은 없다. 그래프에서 노드는 모두 똑같이 취급되며, 단지 서로 다른 방식으로 연결될 뿐이다.

• 그래프 활용 사례
  • 소셜 네트워크
  • 지도 길 찾기
  • 라우팅 알고리즘
  • 추천 알고리즘
  • 그래프 구조로 장르들의 관계를 모형화하여 시각화한 웹 사이트
• 그래프 관련 용어
  • Vertex(정점) : 노드, 위 그림에서 동그라미
  • Edge(간선) : 노드 사이의 연결, 위 그림에서 노드를 잇는 줄
  • Undirected/Directed(무방향, 방향)
    • 무방향 그래프는 양방향 연결이다. 간선에 방향이 없다.
    • 방향 그래프는 간선에 정해진 방향(화살표)이 있다.

• Weighted/Unweightet(가중, 비가중)
  • 가중 그래프는 간선에 값이 부여된 그래프다.

인접 리스트(Adjanceny List)

• 그래프의 노드와 간선 관계를 아래 이미지처럼 해시 테이블을 이용한 인접 리스트로 저장할 수 있다. 만약 아래 예시에서 C노드와 다른 노드들 간 간선을 확인하려면, 인접리스트의 ‘C’ 키에 있는 ['B', 'D'] 밸류를 통해 C 노드는 B노드 및 D노드와 연결되어 있다.
  

그래프의 기본 구조(Constructor)

• 이번엔 무방향 그래프를 만든다.

class Graph {
constructor() {
    this.adjacencyList = {};
  }
}

정점 추가 메서드(addVertex)

• 정점 추가 메서드는, 입력 받은 정점이 인접리스트에 없으면 인접리스트에 정점 key에 빈 배열을 value로 지정해준다.

addVertex(vertex) {
  if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}

간선 추가 메서드(addEdge)

• 간선 추가 메서드는, 추가하려는 간선으로 이어진 두 개의 정점을 입력받고, 이들을 인접리스트에서 서로의 정점의 배열에 push하도록다.

addEdge(vertex1, vertex2) {
  this.adjacencyList[vertex1].push(vertex2);
  this.adjacencyList[vertex2].push(vertex1);
}

간선 제거 메서드(removeEdge)

• 간선 제거 메서드는, 제거하려는 간선으로 이어진 두 개의 정점을 입력받고, 인접리스트의 각각 정점들의 value에서 상대 정점만 제외하여 반환(filter 메서드 사용)된 배열을 재할당한다.

removeEdge(vertex1, vertex2) {
  this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
  this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
}

정점 제거 메서드(removeVertex)

• 정점을 제거하려면, 정점과 연결된 모든 간선들을 제거하고 그 정점도 삭제해야 한다.

removeVertex(vertex) {
// 정점과 연결된 모든 간선을 제거하기 위해 해당 정점의 배열에 대해 루프를 돌면서,
    while (this.adjacencyList[vertex].length) {
// 삭제하려는 정점의 간선들을 removeEdge 메서드를 사용해서 모두 삭제한다.
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
// 정점도 삭제한다.
    delete this.adjacencyList[vertex];
  }

코드 실행 결과

• 해당 클래스의 인스턴스 메서드들을 아래와 같이 실행하면, 주석과 같은 그래프 자료구조가 만들어진다.

const g = new Graph();

g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F