목록알고리즘 (1)

개발 공부~

[자바] 탐색 알고리즘 - DFS, BFS

DFS (깊이 우선 탐색)그래프 완전 탐색 기법 중 하나. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하고 이의 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행-> 한 번 방문한 노드를 다시 방문하면 안됨 -> 노드 방문 여부를 체크할 배열이 필특징재귀함수로 구현 -> stack overflow에 유의!후입선출 -> 스택 자료구조 이용 => 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 문제에 이용됨=> 시간복잡도 = O(V+E) -v: 노드 수, e: 엣지 개수  BFS (너비 우선 탐색)그래프 완전 탐색 기법 중 하나. 그래프의 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘-> 목표 노드에 도착하는 경로가 여러..
IT/JAVA 2024. 7. 22. 18:50
이전 Prev 1 Next 다음