알고리즘) BFS [너비 우선 탐색] 간단 정리

 

• 정의

• 그래프 전체를 탐색
• 루트노드에서 시작하여 인접한 노드를 먼저 탐색.
• 깊게 탐색하기 전에 넓게 탐색하는 것.
• 너비우선탐색이 깊이우선탐색보다 좀 더 복잡.

• 특징

• 재귀적으로 동작 하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했는지 여부를 반드시 검사.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐를 사용

• 구현

• 인접 리스트와 인접 행렬 두 방식으로 구현이 가능
• 인접 행렬
• 모든정점에 대하여 2차원 배열을 생성
• 모든정점에 연결된 다른 정점을 탐색하는 방법.
• 인접 리스트
• 모든 정점에 대하여 존재하는 간선만 탐색을 하는 방법
•  list를 사용
• 그래프내에 적은 간선만을 가지는 경우 인접 리스트로 구현하는것이 유리

 

• 인접리스트를 이용한 코드

public class Bfs {
	private int v;
	private LinkedList<Integer> adj[];
	
	public Bfs(int v) {
		this.v = v;
		adj = new LinkedList[v];
		for(int i = 0 ; i < v ; i++) {
			adj[i] = new LinkedList();
		}
	}
	
	void addEdge(int v, int w) {
		adj[v].add(w);	
		adj[w].add(v);
		
	}
	
	void BFS(int s) { 
		
		boolean visited[] = new boolean[v];
		
		Deque<Integer> que = new ArrayDeque<>();
		
		visited[s] = true;
		que.add(s);
		
		while(!que.isEmpty()) {
			s = que.poll();
			System.out.println(s + " ");
			
			Iterator<Integer> iter = adj[s].iterator();
			
			while(iter.hasNext()) {
				int n = iter.next();
				if(!visited[n]) {
					visited[n] = true;
					que.add(n);
				}
			}
		}
	}
}