<그래프 순회>

그래프 순회(gragh traversal) : 그래프에 있는 모든 정점을 한번씩 방문하는 것

1. 깊이 우선 탐색(DFS, Depth First Search)

 - 더 나아갈 길이 보이지 않을 때까지 깊이 들어간다는 원칙으로 그래프 내의 정점을 방문하는 알고리즘

 - 시작 정점 v를 결정하여 방문

 - 정범 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면 정접 v를 스택에 push하고 w 방문

 - 그리고 w를 v로 하여 다시 두번째 순서 반복

 - 방문하지 않은 정점이 없으면 스택을 pop하여 받은 마지막 방문 정점을 v로 설정

 - 그리고 다시 두번째 순서 수행

 - 스택이 공백이 될 떄까지 두번쨰 순서 수행

2. 너비 우선 탐색 (BFS, Breadth First Search)

 - 시작 정점으로부터 인접한 정점들을 모두 차례로 방문

 - 방문했던 정점을 시작으로 다시 인접한 정점들을 차례로 방문

 - 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문 ( 순회 방법 )

 - 인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입 선출의 구조를 갖는 큐 사용

 - Visit 배열과 Queue 구조로 탐색

 - 시작 정점을 v로 결정 (Queue에 push, visit -> true)

 - v의 인접정점을 탐색하여 있을 경우 v를 pop한 후 v의 모든 인접정점을 Queue에 push

 - visit->true 그 후 더 왼쪽에 있는 정점을 v로 설정

 - 두번째 순서를 반복

 - v의 인접정점을 탐색하여 없을 경우 정점에 방문하지 않는 정점이 있을 경우 pop

오늘 알고리즘 수업에서 수업한 내용임 유익하길래 포스팅해봄 한번씩 읽어보고

이해안되면 검색해보도록 ^*^