그래프 - BFS 탐색 - 인접리스트 vs 인접행렬

탐색은 그래프와 시작점이 주어진다. 

아웃풋 : 그점에서 간선을 타고 갈수있는 모든 위치 ... 이걸 찾고싶다 

 

 

BFS  = 너비우선탐색

B First Search

 

가까이 있는것들로부터 차근차근 퍼져나간다.

호수에 돌을 던지는 모습

(cf. 깊이우선탐색: 개미집)

 

큐 Queue  자료구조 활용하여 탐색  ( FIFO : 선입선출 ) 

(cf. 깊이우선탐색:재귀함수)

 

 

 

*큐에 담긴 자료는 ...  여기를 갈수있다는걸 인지한 상태임을 의미함 

 

새로운 점을 찾을때마다 계속 큐에 넣어준다. 

 

큐에서 원소를 꺼내면 

시작점에서 해당 정점까지 갈 수 있었다는 것을 알게된것임.

 

다시 해당 정점에 연결된 애들을 보면서 큐에 넣어주며

확장해서 탐색   

 

 

BFS 기본코드

def bfs():
	while q: #q 가 비어있지 않다면... 이라는 조건 
    	curr_v= q.popleft()
        
        for next_v in range(1,VERTICES_NUM +1): #꺼낸점과 연결된 모든점을 찾음
        	if graph[curr_v][next_v] and not visited[next_v]: #처음만난 점만 찾는다
                    visited[next_v]] = True
                    q.append(next_v)

 

* q 가 비어있지 않을때  반복하는이유

아직은 더 확장할수있을것 같으니까.. 좀더 탐색해보자 라는 의미

 

 

로직 

q에서 뭔가 꺼냄  ( 얘는 시작점으로부터 방문할수있으니까 들어간거임)

얘한테서 추가로 또 다른 친구들로 갈수있는지 탐색할거임 

 

q 가 빌때까지 계속 탐색하고

q 가 비면 그순간의 visited 배열의 값이 탐색결과임 

 

 

 

 

 

-> 이거도 인접리스트가 편할것같다. 

연결된 정점들을 하나씩 보면서 확장

특정 정점과 연결된 애들을 다 뽑음 

 

 

 

정리

그래프 탐색시 인접리스트를 사용하는게 좋다!! 

어떨땐 DFS 가 좋고, 어떨땐 BFS 가 좋다.

 

그래프 탐색에서는 둘다 똑같지만,,, 

 

각각이 탐색보다 더 많은 부가 효과를 가져옴...  (우리수준에선 너비우선탐색BFS 만 써도 되는거 배우긴함)

 

최근에는 BFS 만 배워도 괜찮음!!! 

 

결론적으로 모든점을 방문한다는 점에서는 같지만,,

방문순서가 다르기때문에 생기는 side effect 가 있음