JavaScript 그래프(Graph)

그래프(Graph)

 자료구조에서 선형 구조는 배열, 연결 리스트, 스택, 큐가 있다. 비선형 자료구조로는 트리와 그래프가 있다. 이번에는 비선형 자료구조중 그래프에 대해서 알아본다.

 그래프란 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형자료구조로 정점 집합과 간선 집합으로 표현할 수 있다.여기서 정점은 노드(Node), 간선은 엣지(Edge)로 표현한다.

 그래프는 여러 특징을 갖고 있는다.

1. 하나의 정점은 같은 정점에 중복되는 간선을 가질 수는 없지만, 다른 정점에 간선을 가질 수 있음으로 하나 이상의 간선을 가질 수 있다.
2. 그래프의 간선 방향 유무에 따라 방향 그래프와 무방향 그래프로 나뉜다. 또한 간선은 가중치를 가질 수 있다.
3. 사이클이 발생할 수 있다. 사이클은 무한 루프를 발생시켜 프로그램의 성능을 저하시킬 수 있음으로 사이클을 찾아서 관리해야 한다.

 그래프는 간선의 방향성, 연결 상태에 따라 분류가 가능하다.

1. 방향성에 의해 방향 그래프와 무방향 그래프로 나눌 수 있다.
2. 연결 상태에 의해 연결 그래프와 비연결 그래프 그리고 완전 그래프로 나눌 수 있다.

자바스크립트에서 그래프 구현하기

인접 행렬 (2차원 배열)

class Graph {
  constructor(numberOfNodes) {
    this.maxSize = numberOfNodes - 1;
    this.graphArray = Array.from(Array(numberOfNodes), () =>
      Array(numberOfNodes).fill(false)
    );
  }
}

Graph.prototype.setNodeConnection = function (start, dest) {
  if (start > this.maxSize || dest > this.maxSize) {
    console.log("can't find node");
    return;
  }
  this.graphArray[start][dest] = true;
};

const graph = new Graph(5);
graph.setNodeConnection(1, 3);
graph.setNodeConnection(2, 4);
console.log(graph.graphArray);

  2차원 배열을 사용해서 방향 그래프를 만들었다. 또한 모든 노드가 연결되어 있지 않음으로 비연결 그래프이다.
만약 방향 그래프를 만든다면

class Graph {
  constructor(numberOfNodes) {
    this.maxSize = numberOfNodes;
    this.graphArray = Array.from(Array(numberOfNodes), () =>
      Array(numberOfNodes).fill(false)
    );
  }
}

Graph.prototype.setNodeConnection = function (start, dest) {
  if (start > this.maxSize || dest > this.maxSize) {
    console.log("can't find node");
    return;
  }
  console.log(this.graphArray[start][dest]);
  this.graphArray[start][dest] = true;
  this.graphArray[dest][start] = true;
};

const graph = new Graph(5);
graph.setNodeConnection(1, 3);
graph.setNodeConnection(2, 4);
graph.setNodeConnection(4, 3);

console.log(graph.graphArray);

  노드를 연결하는 함수에서 도착점에서 시작점으로 연결하는 간선도 추가하면 된다. 이 방법으로 구현하는데 주의할 점은 배열이기 때문에 인덱스가 0부터 시작한다는 점이다. [0]이 첫 번째 노드를 의미한다.

인접 리스트

class Graph {
  constructor(numberOfNodes) {
    this.maxSize = numberOfNodes - 1;
    this.graphArray = Array.from(Array(numberOfNodes), () => []);
  }
}

Graph.prototype.setNodeConnection = function (start, dest) {
  if (start > this.maxSize || dest > this.maxSize) {
    console.log("can't find node");
    return;
  }
  this.graphArray[start][dest] = true;
  this.graphArray[dest][start] = true;
};

const graph = new Graph(5);
graph.setNodeConnection(1, 3);
graph.setNodeConnection(1, 4);
graph.setNodeConnection(1, 2);

console.log(graph.graphArray);

인접 리스트를 사용하는 방법도 인접 행렬을 사용하는 방법과 큰 차이는 없다. 다만 배열은 연결 리스트 처럼 무한정 늘어날 수 있기 때문에 주의해야 한다.