Java로 BFS 구현하기

  Ex) BFS 출력하기

  - vertaxCount(노드의 개수), edgeCount(간선의 개수), startVertax(시작 노드), targerVertax(목적지 노드)를 차례대로 입력 받는다.

  - 그 다음에는 엣지의 순서쌍을 차례대로 입력 받는다.

  - 방문 순서대로 list에 넣고 list에 출력한다.

java

열기 줄바꿈

import java.util.*;
public class BFS1 {
	static int vertaxCount;
	static int edgeCount;
	static int targetVertax;
	static int startVertax;
	static Queue<Integer> queue = new LinkedList<>();
	static ArrayList<Integer> list = new ArrayList<Integer>();
	static boolean [][] edge = new boolean[6][6];
	static boolean [] visited = new boolean[6];
	
	public static void BFSmethod(int vertax) {
		
		visited[vertax] = true;	 	// 방문 처리
		queue.offer(startVertax);
		while(!queue.isEmpty()) {
			
			int currentVertax = queue.poll();
			if( targetVertax == currentVertax ) {
				list.add(currentVertax);
				return;
			}
			
			list.add(currentVertax);	
			for(int i = 1; i <= vertaxCount ; ++i) {
				if(false == visited[i] && true == edge[currentVertax][i]) {
					visited[i] = true;
					queue.offer(i);		//2, 4, 	q = [4  3  5]
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		vertaxCount = scan.nextInt();
		edgeCount = scan.nextInt();
		startVertax = scan.nextInt();
		targetVertax = scan.nextInt();
		for(int i = 0; i < edgeCount; ++i) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			edge[x][y] = true;
		}
		BFSmethod(startVertax);
		for(int i = 0; i < list.size(); ++i) {
			System.out.print(list.get(i) + " ");
		}
	}
}

 

  Note) 입출력 예시

 

  - 입력

5 9
3 5
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5 

 

  - 출력

3 4 2 5