너비 우선 탐색(Breath First Search : BFS) 알고리즘 자바로 구현하기

- 너비 우선 탐색(Breath First Search : BFS)이란?

처음에 방문한 정점과 인접한 정점들을 차례로 방문한다는 점에서 깊이 우선 탐색과 차이가 있습니다. 

먼저 시작점 v를 방문한 후 v에 인접한 모든 정점들을 차례로 방문합니다. 

더 이상 방문할 정점이 없는 경우 다시 v에 인접한 정점 가운데 맨 처음으로 방문한 정점과 인접한 정점들을 차례로 방문하고, 그 다음으로 v에 인접한 정점 중 두 번째로 방문한 정점과 인접한 정점들을 차례로 방문하는 과정을 반복합니다. 

모든 정점들을 방문한 후 탐색을 종료합니다.

 

위의 결과처럼 1->2->4->8->5->3->6->7 순서로 접근합니다. 

 

필요한 변수

- 정점의 passing 여부를 나타내는 vertex 집합

- 정점의 연결 여부를 나타내는 c집합(연결되면 1, 아니면 0)

- 지나온 정점을 저장하는 p 집합<List>

 

핵심

인접한 정점은 1을 기준으로 할 때 2,3이 인접해 있으나 2로 먼저 이동한다고 가정하고 문제를 풀어야 합니다.

재귀함수를 이용해야 하고, 각 vertex집합에 false값이 있다면 인접한 정점을 찾는 로직이 수행됩니다. 

vertex집합의 모든 원소가 true일 경우 정점 탐색 로직을 종료하여 재귀함수 호출을 종료합니다. 

 

출력

지나온 경로를 나타내는 집합 p의 원소들이 출력됩니다. 

 

코드 

DFS코드와 차이가 있습니다.

private ArrayList<Integer> bfs(){

boolean[] vertex = new boolean[9];

int[][] c = {

, , ,

, , ,

, ,

};

vertex[1] = true;

ArrayList<Integer> p = new ArrayList<Integer>();

p.add(1);

recursive(vertex, c, 1, p);

return p;

}

 

private void recursive(boolean[] vertex, int[][] c, int v, ArrayList<Integer> p){

int idx = v;

 

while(isFalse(vertex)){

for(int i=v+1; i<c.length; i++){

if(c[v][i]==1 && !vertex[i]){

idx = i;

break;

}

}

if(vertex[idx])

else{

vertex[idx] = true;

p.add(idx);

recursive(vertex, c, idx, p);

}

}

}

 

private boolean isFalse(boolean[] vertex){

for(int i=1; i<vertex.length; i++){

if(!vertex[i])

return false;

}

 

private static void main(String[] args){

BFS bfs = new BFS();

System.out.println(bfs.bfs());

}

 

 

출력

 

이상으로 BFS 포스팅을 마칩니다. 

 

참고 문헌: DISCRETE MATHEMATICS 이산수학 Express - 7장 그래프 응용, BFS 알고리즘