[Algorithm] BFS (너비 우선 탐색) 알고리즘

• FIFO 탐색 (First In First Out)  <->  DFS:LIFO
• 큐 자료구조 이용
• 시간복잡도: O(V+E)

 

알고리즘 아이디어

1.BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

2.큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입

3.큐 자료구조에 값이 없을 때까지 반복하기

큐에 노드가 없을 때까지 앞선 과정을 반복한다. 선입선출 방식으로 탐색한다.

 

 

수도코드 

Algorithm bfs(g,v)
	visitied[v] = true
    Q.enqueue(v)
    while (Q)
    	v= Q.dequeue()
        for (w adjacent to v)
        	if (!visited[w])
            	visited[w] = true
                Q.enqueue(w)

 

• 참고자료

https://velog.io/@sangmin7648/%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS

깊이우선탐색(DFS)과 너비우선탐색(BFS)

 

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148384