Algorithm | BFS, DFS

업무를 하면서 알고리즘을 사용할일이 상당히 많다고 느꼈다. 학부 시절에 배웠던 BFS, DFS 를 javascript로 구현하는 것을 목표로 구현을 시도해보았다.
(C++이나 Java보다 훨씬 쉽게 구현이 가능하였다!)

BFS & DFS

• BFS : 너비 우선 탐색(BFS, Breadth-First Search)
  BFS 방식 : A - B - C - D - G - H - I - E - F - J 순서로 탐색
• DFS : 깊이 우선 탐색(DFS, Depth-First Search)
  DFS 방식 : A - B - D - E - F - C - G - H - I - J 순서로 탐색

이미지 참조 : https://saegeullee.github.io/algorith

BFS

const graph = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'G', 'H', 'I'],
    D: ['B', 'E', 'F'],
    E: ['D'],
    F: ['D'],
    G: ['C'],
    H: ['C'],
    I: ['C', 'J'],
    J: ['I']
};

const BFS = (graph,node) => {
    let needVisit = [];
    let visited = [];
    needVisit.push(node)

    while (needVisit.length!==0)
    {
        const node = needVisit.shift();

        if (!visited.includes(node))
        {
            visited.push(node)
            needVisit = [...needVisit,...graph[node]]
        }
    }
    console.log("BFS 결과 ",visited)
}

BFS(graph,'A');

DFS

const graph = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'G', 'H', 'I'],
    D: ['B', 'E', 'F'],
    E: ['D'],
    F: ['D'],
    G: ['C'],
    H: ['C'],
    I: ['C', 'J'],
    J: ['I']
};


const DFS = (graph,node) => {
    let needVisit = [];
    let visited = [];
    needVisit.push(node)

    while (needVisit.length!==0)
    {
        const node = needVisit.shift();

        if (!visited.includes(node))
        {
            visited.push(node)
            needVisit = [...graph[node],...needVisit]
        }
    }
    console.log("DFS 결과 : ",visited) 
}

DFS(graph,'A');

결과 콘솔 :