Graph

Graph

Graph 는 정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조이다. 데이터 항목 간의 관계를 나타내는데 사용되며 소셜 네트워크, 교통 네트워크 등과 같은 광범위한 데이터를 나타내는데 사용된다.

보통은 어떠한 목적지에 대한 최단 경로와 지도 등의 연결되어 있는 객채 간의 관계들을 표현할 때 사용한다.

아래는 Javascript 코드로 Graph 자료구조를 구현한 코드이다.

Javascript Code

class Graph {
  constructor() {
    this.vertices = [];
    this.edges = [];
  }

  addVertex(vertex) {
    this.vertices.push(vertex);
  }

  addEdge(vertex1, vertex2) {
    this.edges.push([vertex1, vertex2]);
  }
}

const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");

위의 예에서 Vertex는 꼭짓점 하나의 지점을 나타내느 속성이 있고, Edge는 Vertext 과의 관계를 연결하는 간선을 만들게 된다.

Graph 검색에 대한 알고리즘은 대표적으로 BFS(Breadth Frist Search), DFS(Depth First Search)가 있으며 그 외에도 다익스트라, 크루스칼 등 여러가지 알고리즘이 있다.