[JAVA] BFS(너비 우선 탐색) VS DFS(깊이 우선 탐색)

 

 

 

 

BFS(Breadth-First Search)와 DFS(Depth-First Search)

---

 

 

 

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 그래프나 트리에서 노드를 탐색하는 알고리즘입니다. 오늘은 자바를 사용해서 BFS와 DFS를 구현하는 방법에 대해 알아보겠습니다. 

 

BFS (너비 우선 탐색)

BFS는 시작 노드에서 출발하여 인접한 노드들을 먼저 탐색한 후, 인접 노드의 인접 노드들을 탐색하는 방식입니다. 일반적으로 큐(Queue)를 사용하여 구현합니다.

 

 

1. 특징

• 최단 경로 탐색: BFS는 가중치가 없는 그래프에서 두 노드 간의 최단 경로를 찾을 수 있습니다.
• 너비 우선: 각 단계에서 현재 노드의 모든 인접 노드를 먼저 방문합니다.

 

 

2. 구현

import java.util.*;

public class BFSExample {
    private int V; // 노드의 수
    private LinkedList<Integer> adj[]; // 인접 리스트

    // 생성자
    BFSExample(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 노드를 연결하는 함수
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // BFS 함수
    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        BFSExample g = new BFSExample(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal " +
                           "(starting from vertex 2)");

        g.BFS(2);
    }
}

 

 

 

 

DFS (깊이 우선 탐색)

DFS는 시작 노드에서 출발하여 한 노드를 깊게 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식입니다. 일반적으로 스택(Stack)을 사용하여 구현하며, 재귀를 통해서도 구현할 수 있습니다. 

 

1. 특징

• 경로 탐색: DFS는 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색합니다.
• 깊이 우선: 현재 노드에서 가능한 한 깊게 들어갑니다.

 

 

2. 구현

import java.util.*;

public class DFSExample {
    private int V; // 노드의 수
    private LinkedList<Integer> adj[]; // 인접 리스트

    // 생성자
    DFSExample(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 노드를 연결하는 함수
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // DFS에 의해 사용되는 함수
    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // DFS 함수
    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }

    public static void main(String args[]) {
        DFSExample g = new DFSExample(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal " +
                           "(starting from vertex 2)");

        g.DFS(2);
    }
}