조무위키
조무위키
둘러보기
대문
최근 바뀜
임의의 문서로
미디어위키 도움말
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
특수 문서 목록
문서 정보
행위
문서
토론
편집
역사 보기
DFS
편집하기
경고:
로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다.
로그인
하거나
계정을 생성하면
편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
스팸 방지 검사입니다. 이것을 입력하지
마세요
!
{{공머생}} Depth First Search, 다른 말로 깊이 우선 탐색이라고 한다. 그래프가 있으면 방문 안한것들이 보일 때 마다 방문하는거다. [[BFS]]처럼 가까운 거 먼저 탐색하는게 아니라서 깊은 지점에 있는 것을 탐색할때는 유용하다. 구현할 때 스택 아니면 재귀로 구현하는데 재귀가 훨씬 편하다. 의사코드로 표현하면 다음과 같다. FUNCTION DFS(int src): Mark src as visited FOR i in graph[src]: IF i is not visited: VISIT i C++로 표현하면 다음과 같다. void DFS(int src){ Mark src as visited for(int i = 0;i<graph[src].size();i++){ if(visited[graph[src][i]] == false) DFS(graph[src][i]); } } 그래프 탐색에서는 존나게 중요한 [[알고리즘]] 중 하나로 너비 우선 탐색하고 같이 많이 쓰인다. 보다시피 코드가 짧아서 사실 너비우선탐색보다 구현은 편하다.
요약:
조무위키에서의 모든 기여는 CC BY-SA 4.0 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는
조무위키:저작권
문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다.
저작권이 있는 내용을 허가 없이 저장하지 마세요!
취소
편집 도움말
(새 창에서 열림)
이 문서에서 사용한 틀:
틀:공대생
(
편집
)
틀:공머생
(
편집
)
틀:알림 상자
(
편집
)