CS/Algorithm2 BFS(Breadth First Search) 너비 우선 탐색 IntroductionBFS: 한 우물만 파는 DFS와는 대조적으로, 모든 곳을 똑같이 조금씩 파는 성향 역시 자세한 내용은 여기를 참고하세요. DFS에서는 최근에 방문한 노드부터 보지만, BFS는 먼저 방문한 노드들부터 보기 때문에 Queue를 이용합니다. 1. 시작점을 큐에 넣고 방문했다고 표시2. 큐가 비어있지 않을 때까지 adj(인접행렬) 방문을 시도3. 아직 방문하지 않은 노드일 경우 방문했다고 표시하고 큐에 넣어줌 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include #include using namesp.. 2019. 1. 30. DFS(Depth First Search) 깊이 우선 탐색 IntroductionDFS: 한 우물만 깊게 파다가 막히면 돌아가서 다른 우물을 파는 성향 자세한 내용은 여기가 최고 입니다. 핵심은 방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 것 입니다.재귀 함수도 스택 메모리 공간에 쌓아올려지는 구조이기 때문에 이를 이용해서도 구현 할 수 있습니다. cf) 메모리 구조 아래 코드는 재귀 함수를 통해서 구현한 DFS입니다. adj: 인접 행렬(간선 리스트)addEdge: u와 v 사이의 간선을 설치하기 위한 함수sortList(): 번호가 작은 정점부터 방문하기 위해 정렬하는 함수 DFS1. dfs()라는 함수 내부에서 오버로딩된 dfs()를 이용하여 0번 노드부터 재귀함수로 실행2. 이미 방문한 정점은 다시 방문하지 않으므로 visit.. 2019. 1. 29. 이전 1 다음
