Java로 BFS 구현하기

  Ex)

java

열기 줄바꿈

package first;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BFSpractice0 {
	static int MAX_COUNT = 101;
	static int [][] AdjMatrix = new int [MAX_COUNT][MAX_COUNT];
	static int[] VisitMatrix = new int[MAX_COUNT];
	static int VertaxCount, EdgeCount;
	static Queue<Integer> queue = new LinkedList<>();
	
	public static void main(String[] args) {
		
        int StartV = 1;
		Scanner scan = new Scanner(System.in);
		VertaxCount = scan.nextInt();
		EdgeCount = scan.nextInt();
		for(int i = 0 ; i< EdgeCount; ++i) {
			int V1 = scan.nextInt();
			int V2 = scan.nextInt();	
			AdjMatrix[V1][V2] = 1;
			AdjMatrix[V2][V1] = 1;
		}
		BFSmethod(StartV);
	}
	
	public static void BFSmethod(int _StartVertax) {
		
		VisitMatrix[_StartVertax] = 1;
		queue.add(_StartVertax);
		System.out.printf("%d에서 시작\n", _StartVertax);

		while(false == queue.isEmpty()) {
			int currV = queue.poll();
			for(int i = 1; i <= VertaxCount ;++i) {
				if(0 == VisitMatrix[i] && 1 == AdjMatrix[currV][i]) {
					VisitMatrix[currV] = 1;
					queue.add(i);
					System.out.printf("%d에서 %d로 이동\n", currV, i );
				}
			}
		}
	}	
}

 

 

  Note) 입출력 예시

java

열기 줄바꿈

[입력]
4 4
1 2
1 3
2 4
3 4

[출력]
1에서 시작
1에서 2(으)로 이동
1에서 3(으)로 이동
2에서 4(으)로 이동
3에서 4(으)로 이동


[입력]
6 9
1 2
1 3
2 4
2 5
3 4
3 6
4 5
4 6
5 6

[출력]
1에서 시작
1에서 2(으)로 이동
1에서 3(으)로 이동
2에서 4(으)로 이동
2에서 5(으)로 이동
3에서 4(으)로 이동
3에서 6(으)로 이동
4에서 5(으)로 이동
4에서 6(으)로 이동
5에서 6(으)로 이동
4에서 6(으)로 이동
5에서 6(으)로 이동