728x90 반응형 BFS1 [알고리즘/Python] BFS(너비우선탐색) BFS (너비우선탐색) Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 한다. 데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우 실제 수행시간은 DFS보다 좋은편이다. [DFS vs BFS] 동작 방식 동작 원리 구현 인접한 노드가 여러개라면? DFS 멀리 있는(깊게 있는)노드 부터 탐색 스택 재귀 함수 이용 한개씩 넣음 BFS 가까운 노드부터 탐색 큐 큐 자료구조 이용 한번에 다 넣음 BFS 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다, 3. 2번과정을 더이상 수행할 수 없을 때까지 반.. 2023. 1. 18. 이전 1 다음 728x90 반응형
