BFS(Breath-First Search, 너비우선순회)

그래프 순회

-순회(traversal) :그래프의 모든 노드들을 방문하는 일

-두가지방법

1. BFS(Breath-First Search, 너비우선순회)

2. DFS(Depth-First Search, 깊이우선순회)

너비우선순회(BFS)

■ 큐를 이용한 너비우선순회

1. check the start node(체크는 이미 방문된 노드라는 표시)

2. insert the start node into the queue

3. while the queue is not empty do

remove a node v from queue;

for each unchecked neighbour w of v do

check and insert w into the queue;

반복한다.

노드 방문 순서 : 1,2,3,4,5,7,8,6

■ BFS와 최단경로

- s에서 Li에 속한 노드까지의 최단 경로의 길이는 i이다.

(여기서 경로의 길이는 경로에 속한 에지의 개수를 의미한다.)

- BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.

-입력 : 방향 혹은 무방향 그래프 G=(V,E), 그리고 출발노드 s∈V

-출력 : 모든 노드 v에 대해서

d[v] = s로부터 v까지의 최단 경로의 길이(에지의 개수)

p[v] = s로부터 v까지의 최단경로상에서 v의 직전 노드(prodecessor)

최단경로출력하기