[ 그래프 탐색 ] BFS

BFS 알고리즘으로 트리 탐색 

트리 : 사이클이 없는 부모와 자식관계가 있는 1: N의 관계

 

1. Queue 사용하기 

 

* 슈도 코드 

BFS(v){
	Queue 생성;
    Queue.add(v);
    while(!Queue.isEmpty(){
    	curr = Queue.deq(); // 데이터를 뺀다.
        curr 방문
        For w (curr의 모든자식)
        	Queue.add(w)
	}
}

---

BFS 알고리즘으로 그래프 탐색

트리처럼 하면 stackoverflow 발생

=> 방문했는지 안했는지를 check하는 것이 필요하다.

 

미리 방문처리를 해야한다.

Queue에서 꺼내졌을때 방문처리를 하면 중복된 값이 들어가서 메모리 낭비가 발생한다. 

 

최단거리를 구할때 BFS를 많이 쓴다. 

 

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
	static int N = 7;
	static int[][] adj = { { 0, 1, 1, 0, 0, 1, 0 }, { 1, 0, 0, 1, 0, 0, 1 }, { 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0, 1, 1 }, { 1, 0, 0, 0, 1, 0, 0 }, { 0, 1, 0, 1, 1, 0, 0 } };

	static boolean[] visited = new boolean[N]; 
	static Queue<Integer> queue = new LinkedList<>();

	public static void main(String[] args) {
		BFS(0);
	}

	// v : 시작정점
	static void BFS(int v) {
		// 시작정점을 큐에 넣는다.
		queue.add(v);
		visited[v] = true; 
		while (!queue.isEmpty()) {
			// 정점을 하나 꺼내기
			int t = queue.poll();
			System.out.println(t + 1);

			for (int i = 0; i < adj.length; i++) {
				if (!visited[i] && adj[t][i] == 1) {
					queue.add(i); // 큐에 넣은 후 바로 방문처리
					visited[i] = true;
				}
			}
		}
	}
}