[Java] 그래프 너비 우선 탐색 알고리즘 Breadth-First Search

- 위키백과 -

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

 

그래프의 너비 우선 탐색 알고리즘을 Java로 구현해보자.

 

우선 빈번히 사용 Node 클래스를 작성한다.

 

 

---

 

 

Node.java

public class Node {

	int info;				//정점에 대응된 데이터
	boolean visited;		//방문 여부
	List<Node> neighbours;	//정점에 인접한 정점들의 연결 목록
	
	
	public Node(int info) {	//Node 객체
		this.info = info;
		this.visited = false;
		this.neighbours = new ArrayList<>();
	}
	
	//정점에 인접한 정점들의 연결 목록에 새 정점 추가
	public void addNeighbours(Node neighboursNode) {
		this.neighbours.add(neighboursNode);
	}

	//정점에 인접한 정점들의 연결 목록 반환
	public List<Node> getNeighbours() {
		return neighbours;
	}

	//정점에 인접한 정점들의 연결 목록을 주어진 연결 목록으로 변경
	public void setNeighbours(List<Node> neighbours) {
		this.neighbours = neighbours;
	}
	
	//정점에 대응된 데이터 반환
	public String toString() {
		return "" + info;
	}
}

 

---

BreadthFirstSearch.java

	private Queue<Node> queue;	//방문할 정점 저장하는 큐
	
	public BreadthFirstSearch() {
		queue = new LinkedList<Node>();
	}
	
	public void BFS(Node v) {
		v.visited = true;	
		queue.add(v);	
		
		while(!queue.isEmpty()) {
			
			Node element = queue.remove();
			
			System.out.print(element.info + " ");
            
			List<Node> neighbours = element.getNeighbours();
			
			for(int i = 0; i < neighbours.size(); i++) {
				Node w = neighbours.get(i);
				
				if(w != null && !w.visited) {	//w 방문 안 한 경우
					w.visited = true;	
					queue.add(w);	
				}
			}
		}
	}

v는 방문 여부를 나타내는 변수이다. v가 true라면 큐에 v를 추가한다.

큐가 비어있지 않다면, 즉, 방문할 노드가 남아있다면 큐의 맨 앞에 정점 요소를 끄집어내어 element에 저장하고 element에 대응된 데이터를 출력한다.

이후 element에 인접한 정점들의 연결 목록 끄집어내고, element에 인접한 곳 중에서 방문하지 않은 모든 정점들에 대해 너비우선 탐색 수행한다. 이웃(w)이 방문하지 않은 경우, 방문하고 큐에 w를 추가한다.

 

 

 

 

메인

	public static void main(String[] args) {
		
		//정점 표시
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		
		
		//간선 표시
		node1.addNeighbours(node2);
		node1.addNeighbours(node3);
		node1.addNeighbours(node5);
		node2.addNeighbours(node1);
		node2.addNeighbours(node3);
		node3.addNeighbours(node1);
		node3.addNeighbours(node2);
		node3.addNeighbours(node4);
		node3.addNeighbours(node5);
		node4.addNeighbours(node3);
		node4.addNeighbours(node6);
		node5.addNeighbours(node1);
		node5.addNeighbours(node3);
		node6.addNeighbours(node3);
		node6.addNeighbours(node4);
		
		BreadthFirstSearch bfsExample = new BreadthFirstSearch();
		
		System.out.println("너비 우선 탐색 실행 결과");
		bfsExample.BFS(node1);
	}

 

메인에서 사용할 그래프의 정점과 간선을 설정해준다. 조금만 수정하면 다른 그래프를 만들 수 있어 간편하다.