Graph의 탐색: DFS&BFS

1.그래프 순회

Graph Travesal?

• 그래프에 있는 노드들을 방문하는 과정
• 그래서 traversal의 표현을 가끔씩 검색이나 탐색이라고 표현됨
• 크게 순회에서 쓰는 두 알고리즘
  • BFS(Breadth-first search): 너비우선탐색
  • DFS(Depth-first search): 깊이우선탐색
    

2. BFS

• 너비우선탐색을 하게 되면 말 그대로 넓게넓게 우선적으로 탐색하는 것.
• 그래서 루트노드를 먼저 방문한뒤에 그리고 이것의 자식노드, 그리고 그 자식노드의 자식노드들과 같이 depth 순서대로
• 너비를 우선적으로 고려해서 탐색하기 때문에 결과는 깊이 순서대로 탐색하는 것을 알 수 있다.
• 수도코드

  • choose any vertex, mark it as visited and push it onto queue.
  • While the queue is not empty:
    • Pop a vertex v from the queue
    • for each vertex adjacent to v that has not been visited

• example
  • 임의로 A vertex를 시작vertex로 하고 Queue에 push
    
  • 이 Queue에서 하나의 vertex를 pop. pop했다는 건 이 vertex를 방문했다는 것.
  • A vertex의 인접한 vertex들, Queue에 한번도 방문한 적 없는 vertex들을 Queue에 push
    
  • B가 queue에서 front에 위치하고 있기 때문에 큐에서 빠져나오고, 현재 우리의 경로의 끝에 b를 쓴다. 지금까지 A-B를 순회
  • B의 인접한 C,D 중 C는 Queue에 들어가 있기 때문에 D를 queue에 push
    
  • Queue의 front에 위치한 C를 pop해 주고, 인접한 D,E,F중에 Queue에 한번도 안 들어간 F를 push.
    
  • 그 다음 front에 위치한 E를 pop해 주고 인접하고 방문하지 않았던 G,H를 Queue에 push.
    
  • 그 다음 D도 pop해주고 따로 인접한 vertex가 없기 때문에 F도 pop. F도 인접한 vertex가 없기 때문에 G도 pop해주고 인접하고 방문하지 않았던 I를 queue에 push.
    
    
    
  • 마지막으로 H와 I를 순서대로 pop하면 Queue가 비어있기 때문에 BFS의 순회는 끝이 나게 된다.
    
• 코드 구현

const bfs = (graph, start) => {
    // 방문하지 않은 vertex들을 담을 Queue 생성
    const queue = new Queue();
    // 방문했는지 여부를 체크할 visited set 생성하면 start를 방문의 시작
    const visited = new Set([start]);
    // 시작vertex를 queue에 담고.
    queue.enqueue(start);
  
    //queue가 빌 때까지 반복.
    while(queue.length) {
        //인접한 노드들을 담고
        const neighbors = graph.neighbors(queue.dequeue());
        // 인접한 vertex들을 방문히지 않는 경우엔 queue에 담고 방문 체크하며 반복.
        for(const neighbor of neighbors) {
            if(!visited.has(neighbor)) {
                queue.enqueue(neighbor);
                visited.add(neighbor);
            }
        }
    }
    return visited;
}

3. DFS

• 말 그대로 depth가 깊어지는 순서대로 먼저 탐색을 하겠다는.
• 트리와 같은 그래프에서 위의 그림을 보면, 루트노드로부터 자식노드중 하나인 B, 그리고 깊이를 우선적으로 늘려가는 방향으로
• B에서 깊이가 늘어나는 C,D와 같은 순서대로 탐색하는 것
• BFS는 Queue를 사용, DFS는 Stack을 사용
• 수도코드

  • Choose any vertex, mark is as visitied and push it onto stack
  • While the stack is not empty:
    • pop a vertex v from the stack
    • for each vettex adjacente to v that has not been visited:
      • mark is visited, and
      • push it onto the stack

• example
  
• 코드 구현

const dfs = (graph, start) => {
    // 방문하지 않은 vertex들을 담을 Queue 생성
    const array = new Array();
    // 방문했는지 여부를 체크할 visited set 생성하면 start를 방문의 시작
    const visited = new Set([start]);
    // 시작vertex를 queue에 담고.
    array.push(start);
  
    // stack이 빌 때까지 반복.
    while(array.length) {
        //인접한 노드들을 담고
        const neighbors = graph.neighbors(array.pop());
        // 인접한 vertex들을 방문히지 않는 경우엔 queue에 담고 방문 체크하며 반복.
        for(const neighbor of neighbors) {
            if(!visited.has(neighbor)) {
                array.push(neighbor);
                visited.add(neighbor);
            }
        }
    }
    return visited;
}

참고: 그래프 탐색: DFS와 BFS