[알고리즘] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

DFS (깊이 우선 탐색)

다음 노드로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방식

출처 : https://developer-mac.tistory.com/64

BFS (너비 우선 탐색)

시작 노드에서부터 가까운 노드부터 먼저 탐색하는 방식

출처 : https://developer-mac.tistory.com/64

---

스택을 이용한 DFS(깊이 우선 탐색) 구현

// DFS
    boolean [] visited = new boolean[edges.length];
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);	// 탐색을 시작할 노드 스택에 추가
    while (!stack.isEmpty()) {
        int vertex = stack.pop();
        if (!visited[vertex]) {
            visited[vertex] = true;
            System.out.println(vertex);
        }
        // 스택에 넣은 노드가 나중에 탐색. 역순으로 추가해야 작은 인덱스 노드가 먼저 탐색
        for (int i = edges[vertex].length - 1; i >= 0; i--) {
            if (edges[vertex][i] == 1 && !visited[i]) {
                stack.push(i);
            }
        }
    }

visited : 노드의 방문 여부

 

큐를 이용한 BFS(너비 우선 탐색) 구현

// BFS
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited2 = new boolean[edges.length];

    queue.add(0);	// 탐색 시작 노드 0 큐에 삽입
    visited2[0] = true;

    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        System.out.print(vertex + " - ");

        for (int i = 0; i < edges[vertex].length; i++) {
            if (edges[vertex][i] == 1 && !visited2[i]) {
                queue.add(i);
                visited2[i] = true;
            }
        }
    }

visited2 : 노드의 방문 여부