자료구조 10 그래프 | JS

이미지 출처

그래프 | Graph

• vertex(정점)와 edge(간선)로 구성.
• edge는 vertex와 vertex를 연결

인접 리스트

이미지 출처

• 그래프 내에 적은 숫자의 간선만을 가지는 경우에 용이함
• 각각의 정점에 인접한 정점들을 리스트로 표시
• 배열이나 연결리스트 등을 이용해서 구현이 가능
• 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구, 공간 효율성이 우수
• 각 정점들의 연결 여부 확인을 위해 O(v)의 시간 복잡도

인접 행렬

이미지 출처

• 2차원 배열로 구현
• 그래프에 간선이 많이 존재하는 밀집 그래프의 경우에 용이함
• 선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요
• 특정 노드의 인접 노드들을 탐색하기위해선 모든 노드들을 확인해야 함
• 정점간의 연결여부 확인 시 O(1)의 시간을 요구

그래프 종류

• 무방향 그래프: 간선에 방향이 없는 그래프
• 방향 그래프: 간선에 방향이 있는 그래프(= 다이 그래프)
• 가중 그래프: 간선에 가중치가 있는 그래프(= 네트워크)

그래프 vs 트리

이미지 출처

무방향 그래프 구현

class UndirectedGraph {
  constructor() {
    this.edges = {};
  }
  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = {};
  }

  // 간선 추가하기
  addEdge(vertex1, vertex2, weight = 0) {
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
  }

  // 간선 삭제하기
  removeEdge(vertex1, vertex2) {
    if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
      delete this.edges[vertex1][vertex2];
    }
    if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
      delete this.edges[vertex2][vertex1];
    }
  }

  // 정점 삭제하기 (반대편 정점에서도 간선을 삭제해야함)
  removeVertex(vertex) {
    for (let adjacentVertex in this.edges[vertex]) {
      this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
  }
}

방향 그래프

class DirectedGraph {
  constructor() {
    this.edges = {};
  }
  // 정점 추가
  addVertex(vertex) {
    this.edges[vertex] = {};
  }
  // 간선 추가
  addEdge(from, to, weight = 0) {
    // 시작 정점, 도착 정점, 가중치
    this.edges[from][to] = weight;
  }
  // 간선 삭제
  removeEdge(vertex1, vertex2) {
    if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
      delete this.edges[vertex1][vertex2];
    }
  }
  // 정점 삭제하기 (반대편 정점에서도 간선을 삭제해야함)
  removeVertex(vertex) {
    for (let adjacentVertex in this.edges[vertex]) {
      this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
  }

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
[자료구조] 그래프 (자바스크립트/javascript)

Photo by Alain Pham on Unsplash