목록DFS (1)

말감로그

DFS,BFS, 다익스트라, 플로이드 와샬

그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFS와 BFS로 나뉜다. DFS - 깊이 우선 탐색 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 모든 노드를 방문하고자 하는 경우에 이 방법을 사용 그래프의 구조를 파악하는데 유용 BFS에 비해 간단하지만 검색 속도가 느림 스택 또는 재귀함수로 구현 활용: 미로 찾기 DFS 구현 방법 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노..
이론/자료구조 2024. 2. 7. 21:23
이전 Prev 1 Next 다음