[Algorithm] Breadth-First Search

자신과 연결된 인접 노드를 모두 방문 하는 그래프 완전 탐색 방식

---

BFS 사용 고려 기준

• 양방향 그래프, 사이클이 있는 그래프에서는 제약 조건이 주어지지 않을 경우 무한루프가 발생한다.
• 큐에 들어가는 모든 노드를 한 번씩 방문하기 때문에 방문할 필요가 없는 노드의 정보를 큐에 담지 않는게 좋다.
• 그래프 정보를 인접행렬에 담을 때는 메모리의 낭비가 많고, 노드의 개수가 많아 질 경우 사용이 제한된다.
    ※ 1만개의 노드 정보를 담기 위해 2차원 배열 생성시 380MB 수준의 메모리 소요
• 인접 리스트는 간선 정보가 많을 때 메모리 소비가 늘어나고, 탐색 시간이 오래 걸린다.
• 단 하나의 간선 정보를 관리해야 할 때는 인접 행렬이 용이하다. 

 

샘플 예제 코드

• 노드 정보 입력

// 인접행렬 무가중치
arr[from][to] = 1;
arr[to][from] = 1;
// 인접행렬 가중치
arr[from][to] = 20;
arr[to][from] = 30;

// 인접 리스트 무가중치
ArrayList<Integer> al = new ArrayList<>();
al[from].add(to);
al[to].add(from);
// 인접 리스트 가중치 (Custom Data Type 필요)
ArrayList<Node> al = new ArrayList<>();
al[from].add(New Node(to, cost));
al[to].add(New Node(from, cost));

• 시작 노드 정보를 대기열에 입력

Queue<Integer> q = new ArrayDeque<>();
q.add(start);
dat[start] = 1;

• 대기열의 맨 앞 노드 정보 가져오기 

int now = q.remove();

• 노드의 연결 정보에 있는 모든 노드를 대기열에 입력

for (Integer next : al[now]) {
	if (dat[next] != 0) continue;	// 노드 재방문 방지를 위한 제약조건
    q.add(next);
    dat[next] = 1;
}

전체 코드

ArrayList<Integer>[] al;

static void bfs(int start) {
	Queue<Integer> q = new ArrayDeque<>();
	q.add(start);
	dat[start] = 1;	// DAT
	while(!q.isEmpty()) {
		int now = q.remove();
		for (Integer next : al[now]) {
			if (dat[next] != 0) continue;
			q.add(next);
			dat[next] = 1;
		}
	}
}

public static void main(String[] args) throws IOException{
	int node = Integer.parseInt(br.readLine());
    int edge = Integer.parseInt(br.readLine());
	al = new ArrayList[node + 1];
    for (int i=1; i<node+1; i++) al[i] = new ArrayList<Integer>();
    for (int i=0; i<edge; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			al[from].add(to);
			al[to].add(from);
    }
    
    int start = 0;
    bfs(start);
}