[알고리즘] BFS/DFS (JavaScript)

자료구조 설명

- BFS (Breadth-First Search 너비 우선 탐색) :  가까운 정점부터 탐색므로, 주로 Queue와 함께 사용

- DFS (Depth-First Search 깊이 우선 탐색) : 한 정점 깊이의 끝까지 탐색하므로, 주로 재귀와 함께 사용

 

예시 문제

- 문제 : 무방향 간선들이 주어질 때 연결된 정점의 그룹들이 몇 개인지 반환하는 함수 작성하기 (connectedVertices)

- 전달인자(edges) : 배열 형태로 표현된 시작 점과 도착 점을 엘리먼트로 갖는 2차원 배열

- 출력 값 : 그룹들의 수를 Number 타입으로 리턴

 

connectedVertices([[0, 1],[2, 3],[3, 4],[3, 5],]);  // 2

 

인접 리스트 코드 작성

코드 작성 포인트

1. 인접행렬 만들기

  - 최대 버텍스를 찾기

  - 인접 리스트 만들고 버텍스의 크기만큼 채워주기

  - 전달인자 edges의 엘리먼트를 순회하며 간선 연결하기

 

2. 방문한 vertex를 담을 visited 객체와, 정점 그룹 개수를 세기 위한 count 변수 선언하기

3. BSF/DFS 를 통해서 방문한 정점들을 visited 객체에 담고, count 숫자를 올려주기

4. 아래에서 BSF/DFS 내장함수 만들기

 

코드 작성 (JavaScript)

function connectedVertices(edges) {

  // 최대 버텍스를 찾기
  const maxVertex = edges.reduce((a, c) => {
    const bigger = Math.max(...c);
    if (bigger > a) return bigger;
    return a;
  }, 0);

  // 인접 리스트 만들기 (물론 인접 행렬로도 가능)
  const adjList = {};

  // 인접 리스트에 최대 버텍스 크기만큼 버텍스 만들기
  for (let i = 0; i <= maxVertex; i++) {
    adjList[i] = [];
  }

  // edges의 엘리먼트를 순회하며, 간선을 연결
  for (let i = 0; i < edges.length; i++) {
    adjList[edges[i][0]].push(edges[i][1]);
    adjList[edges[i][1]].push(edges[i][0]);
  }

  // 방문한 버텍스를 담을 객체를 선언
  const visited = {};
  // 버텍스 그룹을 카운트할 변수를 선언
  let count = 0;

  // 그래프에 있는 버텍스를 전부 순회
  for (let vertex = 0; vertex <= maxVertex; vertex++) {

    // 만약 i 번째 버텍스를 방문하지 않았다면 BFS/DFS 로 해당 버텍스 및 연결된 모든 버텍스를 방문
    // BFS/DFS로 갈 수 있는 모든 정점들을 방문하며 visited에 담아짐
    // 방문한 버텍스는 visited에 들어 있어서 if 문을 돌지 않음
    if (!visited[vertex]) {
      bfs(adjList, vertex, visited);   // dfs 사용해도 같은 결과 나옴
      count++;
    }
  }
  return count;
}

 

BSF 내장함수 코드 작성

코드 작성 포인트

1. 함수의 전달인자 : adjList, vertex, visited

2. queue에 vertex를 담아주고, visited 객체에 vertex를 담아주며 값을 true로 설정하기

 

3. queue의 길이가 0일 때까지 순환하기

  - shift() 메소드로 queue에 있는 버텍스를 꺼내오기 (cur 변수로 선언)

  - 반복문으로 cur 정점에 있는 간선들을 전부 순회하기

  - 해당 버텍스를 방문하지 않았다면 queue에 삽입하고, visited 객체에 해당 버텍스를 담아주기

 

코드 작성(JavaScript)

function bfs(adjList, vertex, visited) {

  // queue에 vertex를 담기
  const queue = [vertex];
  // 해당 버텍스를 방문했기 때문에 visited에 담아 주고, 방문했다는 표시인 true를 할당
  visited[vertex] = true;

  // queue의 길이가 0일 때까지 순환합니다.
  while (queue.length > 0) {

    // queue는 선입선출이기에 shift 메소드로 버텍스를 가져오며, cur 변수에 할당
    const cur = queue.shift();

    // 그래프의 cur 정점에 있는 간선들을 전부 순회
    for (let i = 0; i < adjList[cur].length; i++) {
    
      // 정점의 간선을 통해 순회하는 다른 정점
      let nextVertex = adjList[cur][i]

      // 만약, 해당 버텍스를 방문하지 않았다면 queue에 삽입
      // 방문했다는 표시로 visited에 해당 버텍스를 삽입하고 true를 할당
      if (!visited[nextVertex]) {
        queue.push(nextVertex);
        visited[nextVertex] = true;
      }
    }
  // queue가 비어 있다면 더 이상 갈 곳이 없는 것이기 때문에 bfs 함수를 종료하고 카운트를 셈
  }
}

 

DFS 내장함수 코드 작성

코드 작성 포인트

1. 함수의 전달인자 : adjList, vertex, visited

2. visited 객체에 vertex를 담아주며 값을 true로 설정하기

3. 해당 버텍스에 있는 간선들을 전부 순회하기

4. 간선으로 연결된 버텍스를 순회하지 않았다면, dsf를 호출하여 재귀로 방문하기

 

코드 작성(JavaScript)

function dfs(adjList, vertex, visited) {

  // 해당 버텍스에 방문했다는 표시로 visited key에 vertex를 담고 값에 true를 할당
  visited[vertex] = true;

  // 해당 버텍스의 모든 간선들을 전부 순회
  for (let i = 0; i < adjList[vertex].length; i++) {

    // 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면 dfs를 호출해(재귀) 방문
    if (!visited[adjList[vertex][i]]) {
      dfs(adjList, adjList[vertex][i], visited);
	}	 
  }
  // 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트
}