DFS / BFS

📝 간단한 개념정리

• DFS(Depth-First-Search) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
• BFS(Breadth-First-Search) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘.

👆🏻 DFS

• Python으로 구현

# DFS
def dfs(graph, v, visited):
  # 현재노드 방문처리
  visited[v] = True
  print(v, end=' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    # 방문한 노드인지 확인
    if not visited[i]:
      dfs(graph, i, visited)


# 나중에는 입력받는 것
graph = [
         [],
         [2, 3, 8],
         [1, 7],
         [1, 4, 5],
         [3, 5],
         [3, 4],
         [7],
         [2, 7, 8],
         [1, 7]

]


# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * len(graph)

# 정의된 dfs 함수 호출
dfs(graph, 1, visited)

결과값
1 2 7 8 3 4 5

• Javascript로 구현

// DFS

function dfs(graph, v, visited) {
    // 현재노드 방문처리
    visited[v] = true;
    console.log(v);
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    graph[v].forEach(i => {
        // 방문한 노드인지 확인
        if (visited[i] === false) {
            dfs(graph, i, visited);
        }
    });
}

var graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 7, 8],
    [1, 7]
]

var visited = [];

for(var i=0; i < graph.length; i++){
    visited.push(false);
}

dfs(graph, 1, visited);

결과값
1
2
7
8
3
4
5 

🤘🏻 BFS

• Python으로 구현

# BFS

from collections import deque

def bfs(graph, start, visited):
  # 큐 구현을 위해 deque라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문처리
  visited[start] = True
  # 큐가 빌때까지 반복
  while queue:
    # 큐에서 원소 하나를 뽑아 출력
    v = queue.popleft()
    print(v, end=' ')
    # 해당 원소와 연결된 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True




# 나중에는 입력받는 것
graph = [
         [],
         [2, 3, 8],
         [1, 7],
         [1, 4, 5],
         [3, 5],
         [3, 4],
         [7],
         [2, 7, 8],
         [1, 7]

]


# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * len(graph)

# 정의된 dfs 함수 호출
bfs(graph, 1, visited)

결과값
1 2 3 8 7 4 5 

• Javascript로 구현

// BFS

class Queue {
    constructor() {
      this._arr = [];
    }
    enqueue(item) {
      this._arr.push(item);
    }
    dequeue() {
      return this._arr.shift();
    }
}

function bfs(graph, start, visited) {
    const queue = new Queue;
    queue.enqueue(start);
    // 현재노드 방문처리
    visited[start] = true;
    //console.log(`v : ${v}, visited[${v}] : ${visited[v]}, graph[${v}] : ${graph[v]}`)
    // 큐가 빌 때까지 반복
    while(queue._arr.length > 0) {
       // 큐에서 하나의 원소를 뽑아 출력
       var v = queue.dequeue();
       console.log(v);
       // 해당 원소와 연결된 아직 방문하지 않은 원소들을 큐에 삽입
        graph[v].forEach(i => {
            if (visited[i] === false) {
                queue.enqueue(i);
                visited[i] = true;
            }
        });
    }
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문

}

var graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 7, 8],
    [1, 7]
]

var visited = [];

for(var i=0; i < graph.length; i++){
    visited.push(false);
}


bfs(graph, 1, visited);

결과값
1
2
3
8
7
4
5 

※ 주의사항

• 큐를 구현할 때 클래스로 구현해서 while(queue)로만 코드를 작성하면 마지막에 undefined가 출력되면서 forEach부분에서 오류가 남 => while(queue._arr.length > 0)으로 수정했음.

🤲🏻 차이점

• Python에서 각 노드가 방문된 정보를 리스트 자료형으로 표현할 때 visited = [False] * len(graph)로 한 줄로 구현가능함. 그 이유는 * 연산자가 존재하기 때문. 하지만 Javascript에서는 불가능. => 빈 배열을 생성 후 for문으로 graph의 길이 만큼 false를 push()함수로 넣어줌.
• Python에서 for ~ in 문을 Javascript에서는 forEach문을 사용함.
• Python에서 boolean은 True, False로 제일 앞 글자는 대문자이지만 Javascript에서는 boolean은 모두 소문자로 이루어져 있음 => true, false

참고자료

• Javascript while 문 - https://developer.mozilla.org/ko/docs/Web/JavaScript/Guide/Loops_and_iteration#while_%EB%AC%B8
• Javascript forEach문 - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach
• Queue 구현
  • https://helloworldjavascript.net/pages/282-data-structures.html - 내가 사용한 것
  • https://velog.io/@longroadhome/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-JS%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-.%ED%81%90-Queue - Javascript 큐에 대해 잘 설명되어있음.