리스트 (BFS),(DFS)

BFS (너비 우선 탐색), (큐)

1. 처음에 1을 큐에 넣고 방문했다는 표시 남김
2. 큐가 비어있지 않으니 큐의 front인 1번 정점을 꺼낸다
3. 1번 정점과 이웃한 2, 3, 4번 정점은 방문하지 않은 정점이라 큐에 순서대로 넣고 방문처리.
4. 큐가 비어있지 않으니 순서대로 큐의 front정점을 꺼냄
5. 2번은 주변에 방문하지 않은 정점이 없지만 3번은 방문하지 않은 정점 5번을 이웃하고 있어 5번을 큐에 넣고 방문했다는 표시 남김
6. 큐가 비어있을 때 까지 반복

if 연결그래프가 아닐때 BFS순회를 하려면?

for문을 돌면서 아직 방문하지 않은 정점을 찾아 그 정점을 시작정점으로 잡게 코드를 구현하면 된다.

가중치

모든 간선의 길이가 동일한 상황에서 두 지점 사이의 거리를 찾는 문제는 BFS로 처리 가능.
BUT. 모든 간선의 길이가 다르다면 플로이드나 다익스트라와 같은 알고리즘 사용.

DFS(깊이 우선 탐색), (스택)

간단하다. BFS과정에서 큐를 스택으로만 변경하면 끝

재귀가 가능하다. 재귀적으로 함수를 호출하는 상황 = 가장 늦게 호출된 함수를 차례대로 처리. LIFO (스택) but, 재귀로 구현할 때 깊이가 깊어지면 문제가 생길 수 있다.

재귀로 처리하면 실제 방문을 할 때 방문표시를 남긴다.
비재귀적인 방식은 방문하기 전에 방문하지 않은 곳을 발견하면 그 때 방문 표시를 남긴다.
강조
비재귀 DFS는 순회를 잘 수행하지만 엄밀히 말해 우리가 관념적으로 생각하는 DFS와는 방문순서가 다르다.