[자료구조와 알고리즘] 그래프 순회 - 너비 우선 탐색 (bfs)

bfs 탐색

1. 시작 정점 v를 방문한다.
2. v에 인접한 모든 정점들을 방문한다.
3. 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문한다.
4. 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출의 구조를 갖는 Queue를 사용한다.

bfs 탐색 예시

bfs 소스코드

class Graph{
    private ArrayList<ArrayList<Integer>> edges;
    private boolean[] visited;

    public Graph(int size) {
        this.edges = new ArrayList<ArrayList<Integer>>();
        this.visited = new boolean[size];

        for(int i=0;i<=size;i++) {
            edges.add(new ArrayList<>());
        }
    }

    public void addEdge(int start, int end) { // 간선 추가
        edges.get(start).add(end);
        edges.get(end).add(start);
    }

    public void printGraph() { // 그래프 출력
        for(int i=0;i<edges.size()-1;i++) {
            System.out.print("Vertex "+i+"의 인접리스트 -> ");
            for(int j=0;j<edges.get(i).size();j++) {
                System.out.print(edges.get(i).get(j)+" ");
            }
            System.out.println();
        }
    }

    public void clearVisitedArr() { // 방문 배열 초기화
        Arrays.fill(visited, false);
    } 

    public void bfs(int start) { // bfs 탐색
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        visited[start] = true;

        while(!q.isEmpty()) {
            int cur = q.poll();
            System.out.print(cur+" ");

            for(int i=0;i<edges.get(cur).size();i++) {
                int next = edges.get(cur).get(i);

                if(!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
    }

}

public class BfsSearch {

    public static void main(String[] args) {
        Graph graph = new Graph(7);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);
        graph.addEdge(3, 6);
        graph.addEdge(4, 6);
        graph.addEdge(5, 6);

        graph.printGraph();

        graph.clearVisitedArr();

        System.out.print("정점 0부터 탐색: ");
        graph.bfs(0); 
        System.out.println(); 
    }

}