그래프와 bfs, dfs

그래프 (Graph)

여러 노드가 연결되어 있는 관계를 나타낸 비선형 자료구조로 두가지 요소를 통해 표현된다.

• 정점: 데이터를 가지고 있는 노드를 가리킨다.
• 간선: 각 노드를 연결하는 선을 가리킨다.

선으로 연결 되어있는 두 정점을 직접적인 관계를 가진다고 표현하고,
다른 정점을 경유해 접근할 수 있는 경우는 간접적인 관계를 가진다고 표현한다.

용어

• 인접 정점 : 간선을 통해 직접 연결된 정점

• 가중치 그래프 : 연결에 대한 추가적인 정보가 있는 그래프(ex: 정점 사이의 거리/도달 시간)

• 비 가중치 그래프 : 연결에 대한 추가적인 정보가 없는 그래프

• 진입차수(in-degree) / 진출차수(out-degree) : 특정 정점에 입/출 하는 간선의 수

• 자기루프 : 진출한 다음 정점에서 바로 자신으로 돌아오는 과정

• 사이클 : 다른 정점을 통해 자기 자신으로 돌아오는 것

표현 방식

• 인접 행렬
  보통 이차원 배열을 통해 구현하며, 표의 형식으로 정점들의 연결상태를 나타낸다.
  

  [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0]
  ]

  두 정점 사이의 관계 유무를 파악하기 용이하기 때문에 최단 경로를 찾을 때 주로 사용된다.

  • bfs를 통해 그래프 탐색을 시도할 때 인접리스트에 비해 성능이 좋다.

• 인접 리스트
  연결 리스트의 형식으로 정점들의 연결상태를 나타내며, 구현 방식은 사람에 따라 다른 경우가 많고, 연결의 우선순위가 중요하지 않은 방식이다.
  

  {
    A: [B, C],
    B: [A, C],
    C: [A, B, D],
    D: [C]
  }

  연결 가능한 모든 경우를 가지기 때문에 인접 행렬에 비해 적은 메모리를 소모한다.

  그래프 탐색

  그래프는 트리와 달리 사이클이 존재하는 자료구조이기 때문에 탐색시에 탐색을 완료한 노드에 방문했다는 표시를 남겨야 한다. 그렇지 않으면 자기 루프에 영원히 빠질 수도 있다.

  너비 우선 탐색(BFS; Breathed First Search)

  인접한 노드를 우선적으로 접근하는 탐색 방식으로, 최단거리를 찾는 상황에서 주로 쓰인다.
  

  주로 큐를 통해 구현한다.

  const graph = {
    A: ['B', 'C', 'D'],
    B: ['A', 'D', 'E'],
    C: ['A', 'B', 'D', 'E'],
    D: ['A', 'C'],
    E: ['B', 'C'],
  };
  
  const bfs = (vertex) => {
    const visited = [];
    const queue = [];
  
    queue.push(vertex);
  
    while (queue.length !== 0) {
      const node = queue.shift();
      if (!visited.includes(node)) { 
        visited.push(node); // 접근한적 없다면 체크
        for(let i=0;i<graph[node].length; i++) {
         if(!queue.includes(graph[node][i])&&!visited.includes(graph[node][i])) {
           queue.push(graph[node][i]) // 접근한적 없거나 queue에 예약돼있지 않으면 queue에 push한다.
         }
       }
      }
    }
    return visited;
  };
  
  console.log(bfs(graph, 'A'));
  // ['A', 'B', 'C', 'D', 'E']

  깊이 우선 탐색(DFS; Depth First Search)

  마주하는 분기를 우선적으로 접근해 탐색하는 방법으로, 분기하나의 탐색이 끝나야 다른 분기를 탐색한다.
  bfs에 비해 구현이 쉽다는 장점을 가진다.
  

  보통 재귀를 사용하는 방식과 스택을 사용하는 방식 두 가지 중 하나를 통해 구현한다.

  • 재귀를 통한 구현

    const graph = {
      A: ['B', 'D', 'E'],
      B: ['A', 'C', 'D'],
      C: ['B', 'D'],
      D: ['A', 'B', 'C', 'E'],
      E: ['A', 'D'],
    };
    
    function dfs(vertex, result = [], visited = {}) {
      if (graph[vertex].length===0) return;
      visited[vertex] = true;
      result.push(vertex); // 접근한 정점의 값을 출력할 배열에 저장
      graph[vertex].forEach(node => {
        if (!visited[node]) {
          dfs(node, result, visited); // 접근한적 없는 정점이 연결되어 있다면 그 정점으로 넘어간다.
        }
      });
      return result
    } 
    
    console.log(dfs('A'))
    // ['A', 'B', 'C', 'D', 'E']

  • 스택을 통한 구현

    function dfs(vertex) {
      const stack = [vertex];
      const result = [];
      const visited = {};
      visited[vertex] = true;
    
      while (stack.length) {
        let cur = stack.pop(); // 접근할 정점을 최근에 확인한 순서대로 접근한다.
        result.push(cur);
        graph[cur].forEach(node => {
          if (!visited[node]) {
            visited[node] = true; 
            stack.push(node); // 접근한적 없는 정점을 스택에 담는다.
          }
        });
      }
    
      return result;
    }
    
    console.log(dfs('A'))
    // ['A', 'E', 'D', 'C', 'B']

두 방식 모두 dfs지만 시작 방향이 다를 수 있어 결과값이 달라질 수 있다.