1212 깊이우선탐색(DFS)/너비우선탐색(BFS)

그래프
노드와 간선으로 이루어진 자료 구조

깊이우선탐색(DFS)	그래프 완전 탐색 기법 중 하나
	그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후  다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
	스택을 사용

 

동작 방식	탐색 시작 노드를 스택에 삽입하고 방문 처리
	스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 X - 스택에서 최상단 노드를 꺼냄
	더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

깊이 우선 탐색의 구현
	스택에 시작 노드를 넣는다
	스택이 비어 있지 않으면 계속 반복
		스택에서 노드을 하나 pop해서 가져온다
		가져온 노드가 방문한 적 없으면
			방문한 노드 출력
			방문 처리

			방문한 노드의 인접 노드들을 가져온다
			인접 노드들이 방문한 적 없으면 스택에 넣는다.

 

너비우선탐색(BFS)	그래프 완전 탐색 기법 중 하나
	그래프의 시작 노드에서 출발하여 시작 노드를 기준으로  가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
	큐를 사용

동작 방식	탐색 시작 노드를 큐에 삽입하고 방문 처리
	큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
	더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

 너비 우선 탐색의 구현
큐에 시작 노드를 넣는다
시작 노드를 방문처리
큐가 비어 있지 않으면 계속 반복
큐에서 노드을 하나 poll해서 가져온다
가져온 노드 출력
출력한 노드의 인접 노드들을 가져온다
인접 노드들이 방문한 적 없으면 큐에 넣고 방문 처리