BFS,DFS

Bfs와 Dfs는 그래프 전체를 탐색하는 방법이다.

 

BFS 너비 우선 탐색

---

너비 우선 탐색 이란 시작 노드를 방문한 후 시작 노드에 있는 인접한 모든 노드들을 우선 방문하는 방법이다.

시작 노드로부터 가까운 지점을 먼저 방문하고 먼 지점은 나중에 방문한다.

인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용한다.

Bfs방식

큐생성

루트 v를 큐에 삽입

while(큐가 비어있지 않은 경우){

t<-큐의 첫번째 원소 반환

t 방문

for(t와 연결된 모든 간선에 대해){
u<-t의 자식노드

   u를 큐에 삽입  
     }  
 }

 

DFS 깊이 우선 탐색

---

깊이 우선 탐색이란 한방향으로 강수있는 경로가 있는 곳까지 깊이 탐색하는 방법이다.

재귀나 스택을 사용한다.

DFS(v)//매개변수 바뀌는 결정적 요인
v 방문;

for(v의 모든 자식노드 w){
    DFS(w);
}

end DFS()

 

DFS와 BFS의 시간복잡도

---

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

 

DFS BFS 문제 적용

---

• 그래프의 모든 정점을 방문
  Bfs, dfs 모두 가능
• 경로의 특징을 저장
  예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용
• 최단거리
  BFS가 유리하다.
  Dfs로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, Bfs는 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

구현

package algorithm;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//완전이진트리
public class CompleteBinaryTree {

    private char[] nodes;
    private int lastIndex;//마지막 노드의 인덱스
    private final int SIZE;

    public CompleteBinaryTree(int size) {
        SIZE = size;
        nodes= new char[size+1];
    }
    public boolean add(char e) {//완전 이진트리에 맞게 추가
        if(lastIndex==SIZE) {//꽉차서 못넣었으면
            return false;
        }
        nodes[++lastIndex]=e;
        return true;
    }



public void bfs() {
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.offer(1); //루트노드 인덱스부터
    while(!queue.isEmpty()) { //방문대상이 있을 때까지 반복
        int current = queue.poll();//방문차례인 대상 정보 꺼내기
        System.out.print(nodes[current]+" ");//방문해서 해야할일 처리

        //현재 방문노드의 자식들을 대기열에 넣기
        if(current*2<=lastIndex) queue.offer(current*2); //왼쪽 자식
        if(current*2+1<=lastIndex) queue.offer(current*2+1); //오른쪽 자식
    }
    System.out.println();

    }


public void bfs2() {
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.offer(1); //루트노드 인덱스부터
    while(!queue.isEmpty()) { //방문대상이 있을 때까지 반복
        int size = queue.size(); //큐 크기 확인-> 동일 너비 대상 개수

        while(--size>=0) { //반복 진입 전 구한 큐 크기 만큼만 반복
            int current = queue.poll();//방문차례인 대상 정보 꺼내기
            System.out.print(nodes[current]+" ");//방문해서 해야할일 처리

            //현재 방문노드의 자식들을 대기열에 넣기
            if(current*2<=lastIndex) queue.offer(current*2); //왼쪽 자식
            if(current*2+1<=lastIndex) queue.offer(current*2+1); //오른쪽 자식
        }
        System.out.println();
    }
    System.out.println();

    }


public void dfs() {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(1); //루트노드 인덱스부터
    while(!stack.isEmpty()) { //방문대상이 있을 때까지 반복
        int current = stack.pop();//방문차례인 대상 정보 꺼내기
        System.out.print(nodes[current]+" ");//방문해서 해야할일 처리

        //현재 방문노드의 자식들을 대기열에 넣기
        if(current*2<=lastIndex) stack.push(current*2); //왼쪽 자식
        if(current*2+1<=lastIndex) stack.push(current*2+1); //오른쪽 자식
    }
    System.out.println();

    }

public void dfsByPreOrder(int current) {
    System.out.print(nodes[current]+" ");
    if(current*2<=lastIndex) dfsByPreOrder(current*2); //왼쪽 자식
    if(current*2<=lastIndex) dfsByPreOrder(current*2+1); //오른쪽 자식
    }

public void dfsByInOrder(int current) {

//    if(current*2<=lastIndex) dfsByInOrder(current*2); //왼쪽 자식
//    System.out.println(nodes[current]+" ");
//    if(current*2<=lastIndex) dfsByInOrder(current*2+1); //오른쪽 자식

    if(current>lastIndex) return;
    dfsByInOrder(current*2); 
    System.out.print(nodes[current]+" ");
    dfsByInOrder(current*2+1);
    }

public void dfsByPostOrder(int current) {

    if(current>lastIndex) return;
    dfsByPostOrder(current*2); 
    dfsByPostOrder(current*2+1);
    System.out.print(nodes[current]+" ");
    }


}

 

public class CompleteBinaryTreeTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        CompleteBinaryTree tree= new CompleteBinaryTree(9);
        for(int i=0; i<9; i++) {
            tree.add((char)('A'+i));
        }
//        tree.bfs();
//        tree.bfs2();
//        tree.dfs();

        tree.dfsByPreOrder(1);
        System.out.println();
        tree.dfsByInOrder(1);
        System.out.println();
        tree.dfsByPostOrder(1);
        System.out.println();
    }

}