그래프

정의

• 그래프는 정점(Vertex) 과 그 정점을 연결하는 간선(Edge) 으로 구성
• 이러한 정점과 간선의 집합으로 이루어진 자료구조

특징

• 단방향 그래프, 양방향(무방향) 그래프로 나뉨
  • 단방향 그래프: 엣지가 한쪽 방향으로만 연결된 그래프
  • 무방향 그래프: 엣지가 양방향으로 연결된 그래프

활용

• 네이게이션 길찾기

• 게임 내 캐릭터 이동

• 지식 그래프 ⇒ 연관검색어

  • 키워드 기반으로 데이터를 저장하는것이 아닌 키워드 + @로 검색 가능
  

그래프 활용 문제

• 쾨니히스베르크의 다리 문제

  • 한 다리를 두번 이상 건너지 않고 모든 나리를 건널 수 있을까?
  

그래프 종류

방향 그래프

• 화살표로 방향을 표현하며, 방향성이 있는 그래프

• 방향이 있는 그래프는 순서대로만 노드를 이동 가능

• 무방향 그래프는 반대 방향으로도 이동 가능

  

가중치 그래프

• 엣지에 가중치가 주어진 그래프

• 양수 및 음수 가중치 가능

  • 음수 가중치가 있는 경우, 다익스트라 알고리즘을 사용할 수 없으며, 벨만-포드 알고리즘 사용 필요
  

• ex) 1 → 2번으로 바로 가면 6이라는 비용을 소모하지만 1 → 3 → 2번 순서대로 갔을 땐 5라는 비용만 들기 때문에 더 효율적임

순환 그래프

• 어느 한 버텍스에서 어떤 경로를 지나서 다시 그 버텍스로 돌아올 수 있다면 순환 그래프
  

그래프 구현 방법

인접 행렬

• 이차원 배열을 통해 구현
• 장점: 직관적으로 연결 정보를 파악하기 쉽다
• 단점: 메모리 사용량이 크고, 노드 추가 시 복잡도가 증가
  

인접 리스트

• 각각의 노드에 연결된 노드들을 원소로 갖는 리스트
• 장점: 메모리 효율적, 노드 추가/삭제가 수월
• 단점: 연결 관계를 빠르게 파악하기 어렵다
  

js로 구현한 인접 행렬 방식의 그래프

class WeightedGraph {
  constructor(size) {
    this.size = size;
    this.matrix = [];
    this.init();
  }

  init() {
    for (let i = 0; i < this.size; i++) {
      this.matrix[i] = new Array(this.size).fill(Infinity);
    }

    for (let i = 0; i < this.size; i++) {
      this.matrix[i][i] = 0;
    }
  }

  addEdge(from, to, weight = 1) {
    if (from >= this.size || from < 0 || to >= this.size || to < 0) return null;
    this.matrix[from][to] = weight;
  }

  printWeightedGraph() {
    for (let i = 0; i < this.size; i++) {
      console.log(
        this.matrix[i]
          .map((weight) => (weight === Infinity ? '♾️' : weight))
          .join(' '),
      );
    }
  }
}

js로 구현한 인접 리스트 방식의 그래프

class ListGraph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjList.has(vertex)) this.adjList.set(vertex, []);
  }

  addEdge(from, to, weight = 1) {
    if (!this.adjList.has(from)) this.addVertex(from);
    if (!this.adjList.has(to)) this.addVertex(to);

    this.adjList.get(from).push({ node: to, weight: weight });
  }

  printListGraph() {
    for (let [vertex, edges] of this.adjList) {
      let edgeList = edges
        .map((edge) => `${edge.node}(${edge.weight})`)
        .join(', ');
      console.log(`${vertex} -> ${edgeList}`);
    }
  }
}