[알고리즘] 그래프 탐색 알고리즘 - BFS, DFS

오늘은 비선형 구조 중 그래프를 탐색하는 알고리즘을 배워볼 시간이다. 

 

자료구조 
: '데이터의 저장'을 담당하는 것을 말한다.

분류

선형     구조 ) 리스트 , 큐, 스택

비선형 구조 ) 그래프, 트리

파일    구조 ) 순차 파일, 색인 파일, 직접파일

단순     구조 ) 정수, 실수, 문자, 문자열

 

 

알고리즘 
: 표현 및 저장된 데이터를 대상으로 하는 '문제 해결 방법'을 말한다. 

 

 

그래프 탐색 알고리즘

 

그래프 
- 여러 개체들이 연결되어 있는 자료구조

탐색
- 특정 개체를 찾기 위한 알고리즘

 

 예시 

 

 1. 경로 탐색 ( 최단거리 , 시간)

 2. 네트워크  (연결)

 3. 조합         (모든 조합 찾기)

 DFS 

깊이 우선 탐색 알고리즘 

stack을 이용 => list의 경우 push(), pop()을 이용

const graph = {
    //객체를 담아 key.value를 이용한 DFS 풀이
    //인접한 노드를 담은 객체
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "E"],
  D: ["B", "F"],
  E: ["C","G"],
  F: ["D","H","I"],
  G: ["E","J","K"],
  H: ["F","L"],
  I: ["F", "M"],
  J: ["G","N"],
  K: ["G","O"],
  L: ["H"],
  M: ["I","P"],
  N: ["J"],
  O: ["K"],
  P: ["M"]
};
function DFS(graph,start) {
    let 방문O = [];
    let 방문X = [];
    
    방문X.push(start);

    while(방문X.length) {
        const node = 방문X.pop();
        if(!방문O.includes(node)) {
            방문O.push(node);
            //reverse() 제거시 그림 반대로 탐색
            방문X.push(...graph[node].reverse());
        }
    }
    return 방문O;
}

DFS(graph,"A")
(16) ['A', 'B', 'D', 'F', 'H', 'L', 'I', 'M', 'P', 'C', 'E', 'G', 'J', 'N', 'K', 'O']

 

 

 BFS 

넓이 우선 탐색 알고리즘

queue을 이용 => list의 경우 push(), shift() 을 이용

 

DFS - 깊이 우선 탐색 알고리즘	BFS  - 너비 우선 탐색 알고리즘
재귀함수, 스택	큐, 연결 리스트
검증이 쉬움 => easy 문제	시간 복잡도 낮음 => difficult 문제
수행시간 복잡	검증 어려움
O(V+E)	O(V+E)

 

const graph = {
    //객체를 담아 key.value를 이용한 DFS 풀이
    //인접한 노드를 담은 객체
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "E"],
  D: ["B", "F"],
  E: ["C","G"],
  F: ["D","H","I"],
  G: ["E","J","K"],
  H: ["F","L"],
  I: ["F", "M"],
  J: ["G","N"],
  K: ["G","O"],
  L: ["H"],
  M: ["I","P"],
  N: ["J"],
  O: ["K"],
  P: ["M"]
};


function BFS(graph,start) {
    const 방문O = [];
    const 방문X = [];

    방문X.push(start);
    
    while(방문X.length) {
        const node = 방문X.shift();
        if(!방문O.includes(node)) {
            방문O.push(node);
            방문X.push(...graph[node]);
        }
    }
    return 방문O;
}
undefined
console.log(BFS(graph,"A"));
VM3971:1 (16) ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P']

 

참고로 배열에서 스택과 큐의 구현은 아래 글을 봐주시길 바란다.

Array.prototype.push / pop / shift  /unshift

 

스택

후입 선출 즉, push,pop으로 구현할 수 있다.

 

큐

선입 선출 즉 push, shift으로 구현할 수 있다.