java/ds+al/ 너비 우선 탐색 BFS; Breadth First Search

너비 우선 탐색 BFS; Breadth First Search

하나의 정점에서 시작해 (목표를 찾을 때까지) 모든 정점들을 한번씩 탐색한다. 가까운 정점부터 탐색하게 된다.

 

Non-Linear Search Algorithm

1. 데이터(노드)를 하나 불러온다

 

2. 불러온 데이터와 연결된 데이터(노드)를 예약해 대기시킨다

* 이미 불러왔던 데이터라면 다시 불러오지 않는다

 

3. 예약된 데이터(노드)를 하나 불러온다

 

4. 2-3 과정을 예약된 데이터(노드)가 없을 때까지 반복한다

 

---

 

BFS의 전체적인 과정 알아보기

따라서 위와 같이 A, B, C, D, E 노드들을 잇는 간선이 존재한다고 할 때, A부터 시작해 E를 찾는 BFS 알고리즘은 다음과 같이 구현될 수 있다.

 

 

전체적인 탐색 과정은 결국 다음 그림과 같아지게 된다.

 

---

BFS를 코드로 구현해보기

 

일단 정점들과 연결 상태를 표시하기 위한 Node 클래스를 하나 생성한다.

class Node {
    String name; //노드의 이름
    List<Node> links; //노드들의 연결 상태
    boolean visited; //방문 상태

    //생성자로 노드의 이름을 입력받아 name과 links를 초기화한다
    public Node(String name) {
        this.name = name;
        this.links = new LinkedList<>();
    }

    //출력을 위해 toString() 오버라이딩
    @Override
    public String toString() {
        return name;
    }

    //Node의 name을 비교하기 위해 equals() 오버라이딩
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return Objects.equals(name, node.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name);
    }

    //노드를 추가하는 메서드
    void link(Node node) {
        links.add(node);
    }
    
    //방문 여부를 확인하기 위한 메서드
    void visited(){
        this.visited = true;
    }

    boolean isVisited(){
        return this.visited;
    }
}

 

Node 클래스 타입의 데이터를 생성하고, 메서드를 호출해 각각의 연결 상태를 이어준다.

public class BreadthFirstSearch{
    public static void main(String[] args) {
    
        //A, B, C, D, E를 정점으로 한 노드를 생성한다
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");

        //link 메서드를 호출해 각 노드의 연결 상태를 추가해준다
        a.link(b);
        a.link(d);
        
        b.link(c);
        b.link(e);
        
        c.link(b);
        c.link(d);
        
        d.link(a);
        d.link(c);
        d.link(e);
        
        e.link(b);
        e.link(d);
    }
}

 

시작점과 목표점을 입력받아 너비 우선 탐색을 진행하는 메서드를 생성한다.

 public class BreadthFirstSearch{
    //시작점과 찾고자 하는 목표 노드를 parameter로 받는다
    static void bfsQueue(Node start, Node target){
    	//노드들을 대기시킬 큐를 생성하고 시작점을 넣어준다
        Queue<Node> queue = new LinkedList<>();
        queue.offer(start);

        //큐가 빌 때까지 반복한다
        while(!queue.isEmpty()) {
            //노드를 하나 꺼내고, 방문 상태를 true로 변경한다
            Node n = queue.poll();
            n.visited();
            
            System.out.println(n);	//현재 방문 노드를 확인하기 위한 출력

            //꺼내온 노드가 target이라면 확인 출력을 하고 반복을 중단한다
            if (n.equals(target)){
                System.out.println(n + " is found");
                break;
            }
            
            //꺼내온 노드와 연결된 노드가
            n.links.stream()
                    .filter(l -> !l.isVisited()) //방문한 적 없고
                    .filter(l -> !queue.contains(l)) //현재 큐에 없다면
                    .forEach(queue::offer); //큐에 저장한다
        }
    }
}

 

위와 같이 코드를 구현하고, 메인 메서드에서 start를 a로, target을 e로 설정해 메서드를 호출하면 너비 우선 탐색이 이루어지는 과정을 코드로 볼 수 있게 된다.

bfsQueue(a, e);

출력

A
B
D
C
E
E is found