그래프(Graph)란?

그래프는 네트워크 구조를 추상화한 것이다.

컴퓨터과학에서 항목들이 서로 어떻게 연결되어 있는지를 모형화(모델링)하는 방법으로, 소셜 네트워크, 도로, 통신망 등을 표현할때 활용된다.
그래프를 이용해서 특정 정점, 간선, 경로를 검색하고, 최단 경로 찾기 등의 문제를 해결할 수 있다.

그래프는 정점과 간선으로 표현한다.

그래프는 정점과 간선으로 데이터의 연결 관계를 표현한다. 그래서 그래프는 간선으로 연결된 정점의 집합으로 구성되어 있다.

그래프 관련 용어 및 개념

정점 Vertex

노드(Node)라고도 하며, 그래프의 데이터 정보를 가지고 있는 요소이다.

간선 Edge

정점 간의 관계에 대한 정보를 표현한다.

인접 정점 Adjacent Vertex

간선으로 연결된 정점을 인접 정점(adjacent vertex) 또는 이웃(neighbor)이라고 한다.

차수 Degree

인접 정점의 개수를 정점의 차수(degree)라고 한다.

경로 path

한 정점에서 다른 정점으로 연결된 경로들로, 연속된 정점으로 표현된다.

특히 반복된 정점을 포함하지 않는 경로를 '단순 경로(simple path)'라고 한다.

연결됨 Connected

모든 정점 간에 경로가 존재할때 그래프가 연결되었다(connected)라고 한다.

강결합 그래프 vs 스파스 그래프

두 정점이 서로 양방향으로 경로를 갖고 있을때 강결합(strongly connected) 되었다고 한다.

강결합이 아닌 그래프는 스파스 그래프(sparse graph)라고 한다.

사이클 vs 비사이클 그래프

처음과 마지막 정점이 같은, 그래서 마지막 정점 후에 다시 처음 정점으로 돌아오는 단순경로를 사이클(cycle)이라고 한다.

사이클이 없는 그래프는 비사이클 그래프(acyclic graph)라고 한다.

방향 그래프 vs 무방향 그래프

방향 그래프 Directed Graph

간선에 방향성이 있어 화살표가 나아가는 방향의 노드만 이웃(인접 정점)이 된다.

특히 두 정점이 양뱡항으로 경로를 갖고 있을때 강결합되었다(strongly connected)라고 한다.

무방향 그래프 Undirected Graph

간선에 방향이 없는 그래프로, 사실상 화살표가 양쪽에 있는 것(양방향 그래프)와 같다.

가중 그래프 vs 균일 그래프

그래프의 간선에 가중치(Weight)가 있는 그래프를 '가중 그래프'(Weighted Graph)라 하고,
가중치가 없는 그래프를 균일 그래프(unweighted graph)라 한다.

간선에 가중치가 있는 그래프를 가중 그래프라고 한다.

그래프 순회

그래프 순회란 처음 정점을 방문한 이후 아직 탐사할 정점이 남아있는지 계속 추적하는 일이다.
어떤 정점이 있는지, 두 정점사이의 경로를 찾기, 그래프가 연결되었는지, 사이클이 존재하는 지 등을 확인할때 그래프를 순회한다.

그래프를 순회하는 방식에 따라 '너비 우선 탐색(BFS)', '깊이 우선 탐색(DFS)'으로 나뉜다.

각 순회 방식은 아래 별도의 포스트로 정리한다.

• 너비 우선 탐색 BFS
• 깊이 우선 탐색 DFS

인터페이스

• addVertex(val) - 정점을 추가한다.
• addEdge(v, w) - 두 정점(v, w)간에 간선을 추가한다.

구현 - JavaScript에서의 그래프

그래프를 구현하는 방법에는 여러 가지가 있다. 해결하려는 문제와 그래프 유형에 따라 적절한 방법으로 구현하면 된다.

JavaScript는 보통 인접리스트로 구현하므로 인접리스트로의 구현만 해보고 나머지는 방식만 설명한다.

인접리스트(Adjacency List)로 구현

그래프의 구조가 동적인(변하는) 경우 인접리스트로 표현하는 것이 좋다.

각 정점별로 인접정점들의 리스트를 저장한다.
각 정점을 KEY로 하고 인접정점들 값으로 하는 방식으로 배열, 연결리스트, 해시테이블 등을 이용해서 구현한다.

class Graph {
  constructor() {
    // 정점목록
    this.vertices = [];
    // 인접리스트
    this.adjList = {};
  }

  // 정점 추가
  addVertex(v) {
    this.vertices.push(v);
    this.adjList[v] = [];
  }

  // 간선 추가
  addEdge(v, w) {
    this.adjList[v] ? this.adjList[v].push(w) : (this.adjList[v] = []);
    this.adjList[w] ? this.adjList[w].push(v) : (this.adjList[w] = []);
  }
}

// Test
it("Graph 클래스는 잘 동작한다.", () => {
  const graph = new Graph();
  const myVertices = ["A", "B", "C", "D", "E", "F", "G"];
  myVertices.forEach((_, i) => {
    graph.addVertex(myVertices[i]);
  });
  graph.addEdge("A", "B");
  graph.addEdge("A", "C");
  graph.addEdge("A", "D");
  graph.addEdge("C", "D");
  graph.addEdge("C", "G");
  graph.addEdge("D", "E");
  graph.addEdge("B", "F");

  expect(graph.vertices).toEqual(["A", "B", "C", "D", "E", "F", "G"]);
  expect(graph.adjList).toEqual({
    A: ["B", "C", "D"],
    B: ["A", "F"],
    C: ["A", "D", "G"],
    D: ["A", "C", "E"],
    E: ["D"],
    F: ["B"],
    G: ["C"],
  });
});

인접행렬(Adjacency Matrix)로 구현

가장 단순한 구현방법이다.

정점과 다른 정점과의 관계를 2차원배열로 표현한다.
'arr[i][j] === 1'이면 두 노드 사이에 간선이 존재하며 0이면 존재하지 않는 것으로 표현한다.

장점

• 두 정점의 인접 여부를 체크할 때 빠르다.

단점

• 배열이므로 존재하지 않는 간선을 표시하는데 메모리를 소비해야하므로 스파스 그래프라면 적합하지 않다.
• 2차원 배열은 구조가 유연하지 않으므로 정점의 갯수가 계속 변하는 경우 등에는 효과적인 표현방법이라 할 수 는 없다.

근접행렬(Incidence Matrix)로 구현

그래프의 정점을 행으로, 간선을 열로, 두 정점간 연결상태는 2차원 배열로 표시한다.

정점보다 간선이 상대적으로 많은 그래프에서 저장공간과 메모리 절약을 위해 사용된다.

활용 사례

• 우선순위 큐 구현 (가장효율적인 우선순위 큐 구현 자료구조)
• 무손실 압축 알고리즘인 허프만 코드

관련 알고리즘

• 균일 그래프에서 최단경로를 구하는 BFS - BFS(너비 우선 탐색) 문서 참고
• 가중 그래프에서 최단경로를 구하는 다익스트라 알고리즘 - 다익스트라 알고리즘 문서 참고
• 음의 가중치를 가진 그래프에서 최단경로를 구하는 벨만-포드 알고리즘(Bleman-Ford Algorithm)