JS를 사용한 DFS/BFS

인사

안녕하세요! 저는 개발자로 커리어를 다시 시작하는 주니어 프로그래머입니다.
기술 인터뷰 전에 기본 알고리즘을 상기시켜야 할 것 같습니다.
제가 대학에 있을 때 저는 알고리즘, 특히 그래프에 대해 매우 약했습니다.
그래서 다시 배웠고 초보 프로그래머나 초보 프로그래머들과 공유하고 싶습니다.

이 콘텐츠에 포함된 내용

그래프란 무엇인가(간단한 정의)

DFS란 무엇인가/구현하는 방법

BFS란 무엇인가/구현하는 방법

그래프란?

데이터 구조에 대해 알고 있습니까?
데이터 구조는 Array, Linked-List, Stack, Queue, Deck 등과 같이 데이터를 효율적으로 저장하기 위한 구조입니다.

그래프는 정점(노드, 데이터...)과 에지(포인터, 선, 링크..)로 구성된 데이터 구조 중 하나입니다.

아래처럼 보입니다(Vertex는 원, Edge는 녹색 선).



따라서 그래프는 객체 간의 관계를 나타내는 데 좋은 데이터 구조입니다.

DFS란 무엇인가/구현 방법

DFS(Depth First Search)는 그래프 검색을 위한 알고리즘입니다.
DFS는 가능한 한 깊은 노드를 방문합니다.

노드가 다른 노드에 대한 가장자리가 없으면 이전 노드로 돌아가서 동일한 작업을 수행합니다(가능한 한 깊은 노드를 방문).

예를 들어 위 이미지와 같은 그래프와 검색은 'A'로 시작하고

step 1 : visit A, and A has edges to 'F', 'B'
step 2 : visit F, and F has not edge.
step 3 : visit B, and B has edges to 'D' , 'C'
step 4 : visit D, and D has edge to 'E'
step 5 : visit E, and E has not edge.
step 6 : visit C, C has not edge. And it's done.

DFS는 이렇게 작동합니다.

JS로 DFS를 구현하는 방법은 무엇입니까?

위에서 설명한 대로 DFS는 기본적으로 노드를 저장하기 위해 방문/방문 필요 목록이 필요합니다.

처음에는 그래프가 필요하므로 아래에 그래프로 개체를 만들겠습니다.

const graph = {
 'A' : ['F', 'B'], // 'A' has edges to F, B
 'B' : ['D', 'C'], // 'A' has edges to D, C
 'D' : ['E'] // 'D' has edge to 'E'
}

자, 그럼 구현을 시작하겠습니다.

const dfs = (graph, start) => {
  let visited = []; // save a visited nodes 
  let needVisit = [];  // save a need-to-visit nodes

  needVisit.push(start);  // start search with start node

  // looping for need-to-visit list
  while(needVisit.length !== 0) {
    let node = needVisit.shift(); // take a nodes which in first position in array
    if(!visited.includes(node)){ // if this node is not visited,
      visited.push(node); // add to visited list (now visit)

      const tmp = (!graph[node] ? [] : graph[node]) 
      needVisit = [...tmp , ...needVisit] 
// dfs is depth first, So, nodes connected to this node has more high priority than original nodes in need-to-visit list
    }
  }
  return visited.join(' ');
}

BFS란/구현 방법

BFS(Breadth First Search)는 가장 가까운 순서로 노드를 검색합니다.

DFS처럼 'A'로 시작합니다.

step 1 : visit A, and A has edges to 'F', 'B'
step 2 : visit F, and F has not edge. return to 'A'
step 3 : visit B, and B has edges to 'D' , 'C'
step 4 : visit D, and D has edge to 'E'
step 5 : visit C, and C has not edge.
step 6 : visit E, E has not edge. And it's done.

BFS는 이렇게 작동합니다.

JS로 BFS를 구현하는 방법은 무엇입니까?

BFS는 또한 DFS와 같은 노드를 저장하기 위해 방문/방문 필요 목록이 필요합니다.

그래프 객체는 DFS 예제와 동일하며 설명이 있는 코드는 아래에 있습니다.

const bfs = (graph, start) => {
  let visited = []; // save a visited nodes 
  let needVisit = [];  // save a need-to-visit nodes

  needVisit.push(start);  // start search with start node

  // looping for need-to-visit list
  while(needVisit.length !== 0) {
    let node = needVisit.shift(); // take a nodes which in first position in array
    if(!visited.includes(node)){ // if this node is not visited,
      visited.push(node); // add to visited list (now visit)

      const tmp = (!graph[node] ? [] : graph[node]) 
      needVisit = [...needVisit, ...tmp] 
// bfs is breadth first, So, nodes(child nodes) connected to this node has lower priority than original nodes in need-to-visit list
    }
  }
  return visited.join(' ');
}

마치다

실제로 D/BFS는 재귀적인 방식으로 구현할 수 있습니다.
시간 되시면 꼭 드셔보시길 추천합니다.

읽어주셔서 감사합니다. 나쁜 영어로 죄송합니다.
궁금하신 사항은 댓글 달아주시면 아는선에서 답변드리겠습니다.