[탐색] BFS(Breadth-First-Search) : 넓이 우선 탐색

출처 : 나무위키

📌BFS(Breadth-First-Search) : 넓이 우선 탐색

- 그래프 탐색 알고리즘

- 최단 경로를 찾거나 그래프의 모든 노드를 탐색하는 데 사용

- 너비 우선으로 탐색을 진행하는 방식으로, 주어진 그래프에서 시작 노드부터 가까운 노드들부터 차례대로 탐색

- Queue 자료구조를 이용하여 구현

 

 

---

📌 BFS 동작방식

012345678910

1. 시작노드에서부터 탐색 시작

2. 현재 노드의 인접한 노드를 모두 큐에 넣음

3. 큐에서 첫번째 노드를 꺼내어 해당 노드를 방문

4. 그 노드와 연결된 방문하지 않은 노드들을 큐에 추가

5. 큐가 빌 때까지 해당 과정 반복

 

 

---

💡 BFS 구현

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

class Graph {
	// Node 클래스: 그래프의 각 노드를 나타냄
    class Node{
        int data; // 노드의 데이터
        boolean marked; // 노드가 방문되었는지 여부
        LinkedList<Node> adjacent; // 인접 노드를 저장하는 리스트

        Node(int data){
            this.data = data;
            this.marked = false;
            adjacent = new LinkedList<>();
        }
    }
    
    // 노드 배열: 그래프에 포함된 모든 노드를 저장
    Node[] nodes;
    public Graph(int size) {
        nodes = new Node[size];
        for(int i = 0; i < size; i++){
            nodes[i] = new Node(i);
        }
    }
    
	// 간선 추가 메서드: 두 노드를 연결하는 간선을 추가
    void addEdge(int i1, int i2){
        Node n1 = nodes[i1];
        Node n2 = nodes[i2];
        if(!n1.adjacent.contains(n2)){
            n1.adjacent.add(n2);
        }
        if(!n2.adjacent.contains(n1)){
            n2.adjacent.add(n1);
        }
    }

    //BFS 실행 메서드
    void bfs(){
        bfs(0);
    }

    void bfs(int index){
        Node root = nodes[index];
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        root.marked = true;

        while(!queue.isEmpty()){
            Node r = queue.poll();
            for(Node n : r.adjacent){
                if(n.marked == false){
                    queue.offer(n);
                    n.marked = true;
                }
            }
            visit(r);
        }
    }
    
    //방문 및 출력
    void visit(Node n){
        System.out.print(n.data + " ");
    }
}

public class Test {
    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(5, 6);
        graph.addEdge(5, 7);
        graph.addEdge(6, 8);

        graph.bfs();
    }
}

 

---

Reference.

- [자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java