DFS, BFS

DFS, Depth-First Search(깊이 우선 탐색)

1. 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동한다.

2. 시작정점 기준 사전적으로 높은 정점부터 탐색한다.(예외의 경우도 존재)

3. 갈때까지 가보고 막힐경우 다시 돌아온다.

 

BFS, Breadth-First Search(너비 우선 탐색)

1. 시작 정점에서 가까운 정점들을 먼저 방문한다. (N-1)

2. 이후 가장 먼저 방문했던 정점(N)을 시작정점으로 한다.

3. N정점이 1번과정을 마친다. 이후 시작정점은 N+1번 정점이 된다.

 

 

DFS

DFS의 경우 단순하다. 재귀적인 루트만 이해하면  된다.

 

public static void DFS(int index){
    System.out.print(index+" ");
    visited[index] = true;
    for(int i=1;i<=1000;i++){
        if(g[index][i]==1 && !visited[i])
            DFS(i);
    }
}

# 정점의 번호는 순차적이지 않다. 또한 희소행렬 형태로 존재할 수 있다는 가정하에 N<=1000 까지의 조건을 걸었다.

1. index는 최초 시작 정점이다.(메인 함수 접근시에)

2. 최초 시작 정점에 대한 방문여부를 초기화 한다. visited[index] = true;

3. 해당 인덱스와 탐색중인 정점 i 를 잇는 간선이 존재하면(g[index][i] == 1) 그리고 그 정점i를 방문하지 않았다면(!visited[i])

4. 해당 정점에 대해 다시 DFS를 실행한다.

 

BFS

 

BFS의 경우 Queue를 사용해 각 연결된 정점을 queue 에 넣어준다.

1. queue.peek(): 맨 앞의 노드를 리턴, queue.poll(): 맨 앞의 노드를 리턴 후 제거

2. queue.remove(): 맨 앞의 노드를 제거, queue.add(): 노드를 맨 뒤에 삽입

 

 

public static void BFS(int index){
    queue.add(index);
    while(!queue.isEmpty()){
        for(int i=1;i<=1000;i++){
            if(g[queue.peek()][i]==1 && !visited_B[i]){
                queue.add(i);
                visited_B[i] = true;
                g[queue.peek()][i] = 0; g[i][queue.peek()] = 0;
            }
        }
        System.out.print(queue.poll()+" ");
    }
}

# 정점의 번호는 순차적이지 않다. 또한 희소행렬 형태로 존재할 수 있다는 가정하에 N<=1000 까지의 조건을 걸었다.

1. BFS의 경우 queue가 빌때까지 반복문을 돌려준다.(탐색할 정점이 존재하지 않을 때 까지)

2. 먼저 시작정점 index를 큐에 삽입해주고 탐색을 시작한다.

3. BFS와 동일하게 1~1000까지의 정점의여부를 파악하고 간선의 여부를 파악한다.(g[queue.peek()][i] == true?)

4. 방문 여부도 생각한다.

5. 간선이 존재하면 연결된 피정점을 큐에 삽입한다. 이후 간선을 초기화 한다.

6. for 문 완료 후 직전 탐색했던 정점을 출력과 동시에 제거한다.

7. 이후 다음큐에대해서 탐색을 진행한다. 

 

방문

방문여부를 체크(!visited_B[i]) 해주는 것은 BFS중 무한루프에 빠지는 것을 막게해준다.

(1,6) (1,3) (3,1) 일 경우 1에서 시작했다고 가정하자,

1. 1을 탐색하고 3와 6이 큐에 삽입된다. 1에대한 탐색이 종료되고 1이 큐에서 제거된다.

2. 3을 탐색하고 1이 큐에 삽입된다. 3에대한 탐색이 종료되고 3이 큐에서 제거된다.

3. 6을 탐색하고 간선이 존재하지 않으므로 종료된다.

4. 다시 1을 탐색한다, 이후 3과 6이 큐에 삽입된다. 이는 무한히 반복된다.

5. 즉 1의 탐색이 종료 될 때 1에대한 방문여부를 표시해줘야 한다.

 

 

Main

다음은 BFS와 DFS를 입 출력하는 전체 코드이다.

#간선을 입력받을 때 (a, b) 를 입력받고 (b, a) 도 입력하였다. 크게 특별한 것은 없다.

public class Main {
    public static boolean[] visited = new boolean[1001];
    public static boolean[] visited_B = new boolean[1001];
    public static Queue<Integer>queue = new LinkedList<Integer>();
    public static int[][] g = new int[1001][1001];
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(sc.nextLine());
        int N; int M; int V;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        for(int i=0;i<M;i++){
            int a = Integer.parseInt(sc.next());
            int b = Integer.parseInt(sc.next());
            g[a][b] = 1; g[b][a] = 1;
        }
        DFS(V);
        System.out.print("\n");
        BFS(V);
    }
    public static void DFS(int index){...}
    public static void BFS(int index){...}
}