본문 바로가기

(탈퇴) 테슬라's Post

그래프(Graph) - 너비우선검색(BFS)??

자 돌아왔습니다. 점차 불량 마감 작가와 같이 변해가는군요...흑흑

자 오늘은 그래프에서 너비우선검색에 대해서 해보도록 하겠습니다.
자 저번시간에 표현법에 대해서 했지요?
그런데 컴퓨터로 표현해도 결국은 써먹어야겠지요?

트리에서도 했지만 만약에 모든 노드들을 방문해야 한다면...??
그렇지요. 결국은 검색하는 운행법이 있어야겠지요?

트리에는 전위, 중위, 후위, 레벨 운행법이 있었죠?
그런것처럼 그래프에도 크게 너비우선검색(BFS = Breadth First Search)와 깊이우선검색(DFS = Depth First Search)이 있습니다.
오늘은 너비우선검색에 대해서 하도록 하겠습니다.

자 방문을 하려고 한다면? 그렇죠. 시작점이 있어야겠죠?
그런데 우리의 그래프...트리와는 달리 이곳 저곳 연결이 되어있지요?
때문에 그래프는 노드에 방문했었다는 체크표시가 필요합니다.

자 아무튼 시작점에서 시작합니다.
이때 시작점을 방문하고 그 시작점에 연결된 정점들을 모두 방문합니다. 그 후에 방문하지 않은 연결된 정점들에 연결된 정점을 방문하는 것이죠. 음 설명이 짧군요.

자세히 설명한다면 시작점을 선택해서 방문합니다.
방문하는 정점에 연결된 다른 정점중에 방문하지 않은 정점을 큐에 담아둡니다.
큐에서 꺼내면서 이 짓을 반복하는것이지요.

그럼 예를 들어보도록 하도록 하겠습니다.

사용자 삽입 이미지

요런 그래프가 있습니다. 음 모양이 참 예쁘네요.
아무튼 이것을 인접리스트로 표현해보죠.
사용자 삽입 이미지

으아 완전 많군요... 에휴... 맞겠죠...?
자 시작은 친절히 A라고 합시다.
A를 방문합니다. A에 연결된 노드들을 큐에 넣어줍니다.
큐에 넣을때는 방문예정이니까 체크해주세요

사용자 삽입 이미지

A를 방문합니다. 방문한 뒤에 다음 것을 큐에서 꺼내보죠.

B가 나오겠네요. 아하 이런 B에 연결되있는 A는 이미 방문했군요. 다음것을 큐에서 꺼냅시다.

그럼 큐에서 C가 나오겠군요. C에는 A와 D가 연결되있군요.
A는 방문했으니 제외되고 D도 체크 되서 큐에는 안 들어갑니다.

다음에는 D군요. D에 연결되있는 A, C, G 중 A, C를 제외되고,
G는 아직 아무짓도 안했으니 큐에 넣어주고 체크합니다.
사용자 삽입 이미지
자 이제 E를 꺼내봅시다. A, F, G중 A, G를 제외하고 F가 큐에 들어가겠군요.

사용자 삽입 이미지
자 다음 G를 꺼냅니다. D, E 모두 방문했지요.
F를 꺼냅니다. E는 모두 방문했죠?
자 큐에 남은게 없군요. 모두 방문했지요. 순서대로 정리하면
A-> B-> C-> D-> E-> G-> F 겠죠?
음 그래프로 나타내면?

사용자 삽입 이미지
자 이렇게 되는것이죠. 네...맞겠죠...
자 이런식으로 방문하는것이죠...
자 오늘은 여기까지 입니다.
다음은 깊이우선검색을 다루도록 하지요.

오타나 제가 잘못 설명한 부분이 있으면 지적해주세요.
전 여러분의 지적을 받으며 자라난답니다...자라나겠죠? 상처받나...?

'(탈퇴) 테슬라's Post' 카테고리의 다른 글

그래프(Graph) - 깊이우선검색(DFS)??  (5) 2009.02.18
Tesla's Post 공지  (0) 2009.02.17
그래프(Graph) - 표현법??  (0) 2009.02.05
Tesla's Post 연기 됩니다.  (0) 2009.01.25
그래프(Graph) - 그래프??  (2) 2009.01.20