[Java] BFS 구현하기 - 재귀 함수&Queue이용 / 인접 리스트

ex)

출처: https://scshim.tistory.com/241

 

---

                                                                  Code                                                                     

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static LinkedList<Integer>[] adj;
    static boolean[] visit;
    static Queue<Integer> queue;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        //정점과 간선 선언 및 저장
        String str = bf.readLine();
        int n = Integer.parseInt(str.split(" ")[0]);
        int m = Integer.parseInt(str.split(" ")[1]);

        queue = new LinkedList<>();

        //t,f판별 배열과 인접 리스트 선언 및 초기화
        visit = new boolean[n+1];
        adj = new LinkedList[n+1];
        for (int i = 0; i<adj.length; i++){
            adj[i] = new LinkedList<>();
        }

        //인접 리스트 값 입력 및 노드에 값 저장
        for (int i = 0; i < m; i++){
            String str2 = bf.readLine();
            int u = Integer.parseInt(str2.split(" ")[0]);
            int v = Integer.parseInt(str2.split(" ")[1]);
            adj[u].add(v);
            adj[v].add(u);
        }

        //t, f판별 후 bfs실행
        for (int i = 1; i<n+1; i++){
            if (!visit[i])  {
                visit[i] = true;
                System.out.print(i + " ");
                bfs(i);
            }
        }
    }

    //bfs함수
    private static void bfs(int i) {
        for (int a:adj[i]) {
            if (!visit[a]) {
                visit[a] = true;
                queue.add(a);
                System.out.print(a + " ");
            }
        }
        if (!(queue.isEmpty())) bfs(queue.poll());
        else return;
    }
}

 

---

                                                                  결과                                                                      

입력

출력