[javascript] 그래프와 트리 알고리즘

18 Dec 2023

javascript

그래프와 트리는 컴퓨터 과학과 소프트웨어 공학에서 중요한 개념입니다. 이들은 데이터 구조와 알고리즘에서 널리 사용되며 많은 문제들을 해결하는 데 활용됩니다.

그래프

그래프(graph)는 정점(vertex)과 간선(edge)으로 이루어진 형태의 자료구조를 말합니다. 그래프는 네트워크 모델이나 맵, 지하철 노선도 등을 표현하는 데 사용됩니다.
그래프의 간선은 방향성과 가중치를 가질 수 있습니다. 이러한 특징에 따라 그래프는 방향그래프(directed graph)와 가중치 그래프(weighted graph)로 나눌 수 있습니다.
그래프 알고리즘은 최단 경로, 최소 스패닝 트리, 네트워크 유량 등 다양한 문제를 해결하는 데 사용됩니다.

다음은 간단한 그래프의 표현 방법을 보여주는 JavaScript 코드입니다.

class Graph {
  constructor() {
    this.vertices = [];
    this.adjacencyList = new Map();
  }

  addVertex(v) {
    this.vertices.push(v);
    this.adjacencyList.set(v, []);
  }

  addEdge(v, w) {
    this.adjacencyList.get(v).push(w);
    this.adjacencyList.get(w).push(v);
  }
}

트리

트리(tree)는 계층적인 구조를 표현하는 데 사용되며, 그래프의 한 종류로 볼 수 있습니다. 트리는 하나의 루트 노드(root node)와 이에 연결된 자식 노드들로 이루어져 있습니다.
이진 트리(binary tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 트리를 기반으로 하는 다양한 알고리즘이 개발되어 있습니다.
트리 알고리즘은 이진 탐색 트리, 깊이 우선 탐색, 너비 우선 탐색, 힙(heap) 등의 주제를 다루며, 데이터의 삽입, 삭제, 검색, 정렬 등을 효율적으로 수행할 수 있도록 도와줍니다.

아래는 이진 탐색 트리를 구현하는 간단한 JavaScript 코드입니다.

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    let newNode = new Node(data);
    if (this.root === null) this.root = newNode;
    else this.insertNode(this.root, newNode);
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) node.left = newNode;
      else this.insertNode(node.left, newNode);
    } else {
      if (node.right === null) node.right = newNode;
      else this.insertNode(node.right, newNode);
    }
  }
}

그래프와 트리 알고리즘은 다양한 분야에서 활용되며, 프로그래밍 공부를 할 때 중요한 개념이니 꼭 숙지해두시기를 권장드립니다.

더 많은 정보를 원하시면 다음 자료들을 참고하시기 바랍니다.