그래프 (Graph)

Graph

그래프(Graph)는 노드와 간선으로 표현된 자료구조입니다. 그래프에서 노드는 정점이라 불리며, 각 정점은 간선으로 연결되어 있습니다. 정점은 도시로, 간선은 도시 간 이동을 위해 연결된 길로 생각하면 이해하기 쉽습니다. 그래프는 다른 자료구조와 달리 현실 세계를 표현하기 좋습니다. 정점과 간선을 도시와 길로 비유할 수 있듯, 이를 바탕으로 현실 세계를 모델링하면 대표적으로 네비게이션과 같은 시스템을 만들 수 있습니다. 만약 현실에서 마주하는 다양한 문제를 해결하고 싶다면, 그래프는 반드시 이해하고 넘어가야 하는 중요한 자료구조 중 하나입니다.

그래프에서는 다음 용어들을 사용합니다.

• 정점(Vertex): 하나의 노드
• 간선(Edge): 두 정점을 연결한 선
• 가중치(Weight): 간선이 가지는 값
• 사이클(Cycle): 정점과 간선으로 이루어진 경로 중 하나의 정점을 두 번 이상 지나는 경우
• 인접(Adjacency): 간선으로 연결된 두 정점의 관계 (Ex. A와 B는 인접하다)
• 방향성(Directed): 간선이 방향성을 가진 경우 (Ex. A->B)
• 무방향성(Undirected): 간선이 방향성을 가지지 않은 경우 (Ex. A-B)

그래프를 만드는 방법에는 크게 인접 행렬과 인접 리스트를 이용하는 두 가지 방법이 있습니다.

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

두 가지 방법 모두 장단점이 확실하기 때문에, 어느 한 쪽이 뛰어나다 할 수는 없습니다. 인접 행렬은 탐색 속도가 정말 빠르지만, 행렬이기 때문에 초기 정점의 개수를 초과해서 만들 수 없습니다. 반면 인접 리스트는 리스트의 특성 그대로 순차 탐색을 하기 때문에 속도는 행렬에 비해 느리지만, 공간적 제약이 없다는 장점이 있습니다.

인접 행렬 그래프

class AdcacencyMatrix {
  constructor(v, type) {
    this.graph = Array.from({ length: v }, () => Array.from({ length: v }, () => -1));
    // 방향성 (Directed, Undirected)
    this.type = type;
  }

  connect(from, to, weight) {
    this.graph[from][to] = weight;
    if (this.type === 'undirected') {
      this.graph[to][from] = weight;
    }
  }

  print() {
    this.graph.forEach((adj, from) => {
      process.stdout.write(`${from}: `);
      adj.forEach((w, to) => (w !== -1 ? process.stdout.write(`[${to}, ${w}] `) : null));
      console.log();
    });
  }
}

const matrix = new AdcacencyMatrix(5, 'undirected');

// 0번 정점과 4번 정점을 1의 가중치로 연결
matrix.connect(0, 4, 1);
// 0번 정점과 4번 정점을 7의 가중치로 연결
matrix.connect(2, 4, 7);

matrix.print();

초기 정점의 개수만큼 행렬에 공간을 마련했으며, 전부 -1로 초기화했습니다. 일반적으로 두 정점간 거리는 음수가 될 수 없기에 이렇게 표현했지만, 가질 수 없는 값인 무한(Infinity)으로 연결되어 있지 않은 것을 표현해도 됩니다.

인접 리스트 그래프

class AdcacencyList {
  constructor(v) {
    // 동일하게 배열을 사용하지만, 실제 연결 관계만 담음
    this.graph = Array.from({ length: v }, () => []);
  }

  connect(from, to, weight) {
    this.graph[from].push([to, weight]);
  }

  print() {
    this.graph.forEach((adj, from) => {
      process.stdout.write(`${from}: `);
      console.log(adj);
    });
  }
}

const list = new AdcacencyList(5);

list.connect(0, 1, 1);
list.connect(0, 2, 1);
list.connect(0, 3, 1);
list.connect(0, 4, 1);
list.connect(1, 3, 1);
list.connect(2, 4, 1);
list.print();

인접 리스트를 표현할 때도 내부에서는 배열을 통해 그래프 정보를 담을 수 있습니다. 하지만 모든 정점의 모든 간선 정보를 담고 있던 인접 행렬과 달리, 실제로 연결된 관계만 담는다는 차이가 있습니다.

References 📝

본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️