그래프(Graph)

그래프(Graph)는 정점(Vertex) 간선(Edge)으로 이루어진 비선형 자료구조이다.
때문에 그래프(Graph)와 트리(Tree)는 정점의 관계를 표현하는 자료구조라는 점에서 동류라고 볼 수 있다.

용어

• 정점(vertex)
  - 노드(node)라고도 하며 각 정점에는 데이터가 저장된다.
• 간선(edge)
  - 링크(arcs)라고도 하며 각 정점간 관계를 의미한다.
  

구현 방식

인접행렬(Adjacency Matrix)

2차원 배열에 각 정점이 연결된 형태를 표현하는 방식이다.

장점

1. 구현이 빠르다.
2. 검색 속도가 O(1)로, 빠르다.

단점

1. 생성 시 O(n^2)의 시간 복잡도를 갖는다.
2. 무조건 2차원 배열 이상의 공간이 필요하기에, 공간 낭비가 심하다.

인접리스트(Adjacency List)

모든 정점에 연결된 정점들을 리스트로 표현하는 방식이다.

장점

1. 검색 속도가 O(n)으로, 빠른 편이다.
2. 필요한 만큼만 공간을 사용하기 때문에, 공간 낭비가 적다.

단점

1. 검색 속도가 인접행렬(Adjacency Matrix)에 비해 느리다.
2. 구현이 비교적 어렵다.

그래프(Graph)의 종류

무방향 그래프 (Undirected Graph)

정점을 연결하는 간선에 방향이 없는 그래프를 말한다.

방향 그래프 (Directed Graph)

정점을 연결하는 간선에 방향이 있는 그래프를 말한다.
간선의 방향대로만 이동할 수 있다.

가중치 그래프 (Weighted Graph)

두 정점을 이동하는 비용이 존재하는 그래프를 말한다.

완전 그래프 (Completed Graph)

모든 정점이 연결되어있는 그래프를 말한다.

그래프(Graph)의 탐색

그래프의 모든 정점을 한 번씩 방문하는 것을 탐색이라고 한다.

DFS와 BFS 관련된 자세한 내용은 추후 알고리즘 파트에서 다루도록 한다.

깊이 우선 탐색(Depth-First Search)

그래프의 가장 깊은 곳 까지 내려간 후, 더 이상 내려갈 정점이 없으면 옆으로 이동하는 탐색 기법

• 재귀 호출
• 스택(Stack)

너비 우선 탐색(Breadth-First Search)

그래프에서 최대한 넓게 이동한 후, 더 이상 이동할 정점이 없으면 내려가는 탐색 기법

• 큐(Queue)

자바스크립트와 그래프(Graph)

class Graph {
  constructor() {
    //기본 생성자
    this.nodes = {};
  }

  addNode(node) {
    //노드 추가
    this.nodes[node] = this.nodes[node] || [];
  }

  contains(node) {
    //그래프에 해당 노드가 존재하는지 여부
    let result = null;
    this.nodes[node] ? (result = true) : (result = false);
    return result;
  }

  removeNode(node) {
    //노드 삭제
    this.nodes[node] ? delete this.nodes[node] : this.nodes[node];
  }

  hasEdge(fromNode, toNode) {
    //두 노드 사이 간선의 존재 여부
    let result = null;
    this.nodes[fromNode] &&
    this.nodes[toNode] &&
    this.nodes[fromNode].includes(toNode) &&
    this.nodes[toNode].includes(fromNode)
      ? (result = true)
      : (result = false);
    return result;
  }

  addEdge(fromNode, toNode) {
    //두 노드 사이에 간선 추가
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

  removeEdge(fromNode, toNode) {
    //두 노드 사이 간선을 삭제
    let node = this.nodes[fromNode];
    if (
      this.nodes[fromNode].includes(toNode) &&
      this.nodes[toNode].includes(fromNode)
    ) {
      this.nodes[fromNode][node.indexOf(toNode)] = "";
      this.nodes[toNode][node.indexOf(fromNode)] = "";
    }
  }
}

const graph = new Graph();
graph.addNode(100);
graph.addNode(1);
graph.addNode(200);
graph.addNode(400);
graph.addEdge(100, 400);
graph.addEdge(400, 200);
console.log(graph);

/**
Graph {
  nodes: { '1': [], '100': [ 400 ], '200': [ 400 ], '400': [ 100, 200 ] }     
}
*/

Reference

비선형 자료구조 - 그래프(Graph)
[Algorithm] 자료구조 그래프(Graph)란 무엇인가?
[11] [알고리즘 - 자료구조] 그래프(graph)란? (비선형구조) javascript 구현
[Data Structure] 자바스크립트로 그래프 Graph 구현하기