BFS . 5

 

BFS 유형은 최단 거리 유형의 문제에 활용되기도 한다

 

 

 

 

 

 

모든 작업이 끝나면 큐 안은 비워져 있다.

 

 

 

 

 

BFS 코드 예제 :  DFS 와 마찬가지로 BFS 도 0번 인덱스를 비워두고, visited 배열의 요소를 9개로 선언한다

 

 

 

파이썬 예제

queue = deque([start])   # 시작 노드를 큐에 넣어준다 
파이썬 deque 를 출력해보면  deque([1,2])  이런 형태로 출력이 된다. 
(큐의 요소 하나가 리스트 하나인 느낌)

while queue   # 큐가 참일 때 --> 큐가 0이 아닐 때 --> 큐가 비어있지 않을 때

(popleft 함수는 반환까지 하는 함수인듯)

 

 

 

 

 

c++ 예제
c++ 에서 인접리스트 방식으로 그래프를 구현하고자 하면 vector를 이용해서 
특정 노드에 연결되어 있는 인접 노드들의 리스트를 표현할 수 있다.

front(), push() 함수 활용

 

 

 

 

자바 예제
ArrayList 는 특정 인덱스에 접근하기 위해 상수시간이 소요되기 때문에 일반 배열보다 더 좋다

ArrayList를 중첩된 형태로 이용해서 그래프를 표현할 수 있다

자바에서는 LinkedList 로 구현된 큐를 이용한다.

offer, poll, get 함수 활용
자바에서 ArrayList를 이용할 때 특정 인덱스의 요소를 가져오기 위해서는 get 메서드를 사용해야 한다