그래프는 유한하고 변할 수 있는 꼭지점이나 노드나 점들의 집합으로 구성된 데이터 구조다.
sns나 지도기능(최단거리 찾기), 구글지도나 방향안내, 위치, 길 찾기 추천 상품 등 거의 모든 영역에 쓰인다.

그래프는 Vertex(node)와 Edge(connection between nodes)로 구성되어 있으며 아래의 기준에 따라 분류한다.

weighted / Unweightes - values assigned to distances between vertices
e.g) 지도상의 거리
Directed / Undirected - directions assigned to distanced between vertices
e.g) 팔로잉 팔로우

Adjacency Matrix

위처럼 그래프의 노드들간의 관계를 행렬로 표현할 수 있다.

Adjacency list

이렇게 해시테이블로도 그래프를 표현할 수 있다.

표를 보면 전체 순회 시에는 Adjacency list, 검색할 때는 adjacency Matrix를 활용하는게 유리하다.

코드

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) { // 정점추가
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  removeVertex(vertex) { 
    while (this.adjacencyList[vertex].length) {
      // 먼저 정점의 전체 요소를 순회한다.
      // 하나씩 순회하며 인접 정점을 담은 후 인접 정점과 연결된 간선을 삭제한다.
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    // 모든 간선을 삭제시킨 후에 정점을 삭제한다.
    delete this.adjacencyList[vertex];
  }

  addEdge(v1, v2) { // 간선추가
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      v => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      v => v !== vertex1
    );
  }
}

let g = new Graph();
g.addVertex("Dallas");
g.addVertex("Tokyo");
g.addVertex("Aspen");

g.addEdge("Dallas", "Tokyo");

g.removeEdge("Dallas", "Tokyo");
console.log(g);

그래프 순회

그래프는 정점-정점의 정점 - 정점의 정점의 정점 ... 패턴으로 순회하는 DFS와 정점의 모든 정점 순회 후 정점의 정점을 순회하는 BFS로 순회한다.

  dfsr(start) { // 재귀형
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) return dfs(neighbor);
      });
    })(start);
    return result;
  }

  dfsi(start) { // 반복형
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;
    while (stack.length) {
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor)
        }
      })
    }
    return result;
  }

  bfs(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;
    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      })
    }
    return result;
  }