728x90

목록BFS (1)

728x90

내 세상

[Algorithms] DFS, BFS, Dijkstra, Bellman-Ford, Floyd, Heap

DFS (Depth-First Search, 깊이 우선 탐색) - 방식 : - 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. - 역추적(Backtracking) 과정이 있어 Stack / Recursion을 사용 - 자기 자신을 호출하는 순환 알고리즘의 형태 - 사용 예시 - 미로 생성 - Cycle Detection - Topological Sorting - 시간복잡도 (정점 N, 간선 E) - 인접 리스트로 표현된 그래프 O(N+E) - 인접 행렬로 표현된 그래프 O(N^2) - 장점 - 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. - 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있음. → 임의로 지정한 ..
Coding/Algorithms 2019. 4. 30. 23:31
이전 Prev 1 Next 다음