[graph] 너비 우선 탐색(BFS, Breadth First Search)

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

시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법

가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법

인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출(First-IN First-Out) 구조인 큐(Queue) 사용

---

BFS 수행순서

큐가 공백이 될 때까지 빨간 상자 부분을 반복한다.

---

BFS 과정 표현

초기 상태

↓

정점 1 방문 → 인접 정점 [2, 4]

↓

정점 2, 4 방문 → enQueue()

↓

deQueue() → 정점 2의 인접 정점 [3, 5]

↓

정점 3, 5 방문 → enQueue()

↓

deQueue() → 정점 4의 인접 정점 없음

↓

deQueue() → 정점 3의 인접 정점 없음

↓

deQueue() → 정점 5의 인접 정점 없음

↓

Queue가 비었으므로 탐색 종료

결과 : 1 → 2 → 4 → 3 → 5

---

인접 행렬로 구현한 그래프 BFS

    static void BFS(int[][] graph, int v) {
        //큐를 이용한 BFS
        Queue<Integer> queue = new LinkedList<>();
        boolean visited[] = new boolean[graph.length]; // 방문 여부를 검사할 배열

        //처음 탐색할 정점 v
        queue.offer(v); //enQueue()
        visited[v] = true;
        System.out.print("BFS 탐색 순서 : " + v);

        while(!queue.isEmpty()){
            int w = queue.poll(); //deQueue()
            for(int i = 1; i < graph.length; i++) { //w에 인접한 모든 정점을 먼저 방문한다.
                if(graph[w][i] == 1 && !visited[i]) {
                    queue.offer(i); //enQueue()
                    visited[i] = true;
                    System.out.print(" -> " + i);
                }
            }
        }
    }

BFS 실행 결과

---

인접 리스트로 구현한 그래프 BFS

    public void BFS(int v, int n){ //시작 정점 v, 정점의 개수 n
        Queue<Integer> queue = new LinkedList<>();
        boolean visited[] = new boolean[n+1]; // 방문 여부를 검사할 배열

        //탐색 시작 정점
        queue.offer(v); //enQueue()
        visited[v] = true;
        System.out.print("BFS 탐색 순서: " + v);

        while(!queue.isEmpty()) {
            v = queue.poll(); //deQueue()
            //v에 연결된 정점들 모두 반복하도록 한다.
            for(gNode w = head[v]; w != null; w = w.link){
                if(!visited[w.vertex]){
                    visited[w.vertex] = true;
                    queue.offer(w.vertex); //enQueue()
                    System.out.print(" -> " + w.vertex);
                }
            }
        }

BFS 실행 결과

---

전체 코드 정리
https://github.com/ChoSooBeen/graph/tree/main/src

GitHub - ChoSooBeen/graph: graph - data structure study code