반응형 [C++로 배우는 알고리즘과 자료구조] Day 24: 너비 우선 탐색 (BFS) 너비 우선 탐색 (BFS, Breadth-First Search)너비 우선 탐색(BFS)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 인접한 정점들을 모두 탐색한 후, 탐색이 끝난 정점의 인접 정점을 탐색하는 방식입니다. BFS는 큐 자료구조를 사용하여 구현할 수 있습니다.BFS의 주요 특징:시간 복잡도: (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.공간 복잡도: (O(V)), 큐와 방문 여부를 저장하는 배열의 크기입니다.BFS 구현그래프 구현 (인접 리스트 사용)#include #include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(i.. 2024. 8. 1. [알고리즘] 7. 그래프 탐색 Index 1. 스택과 큐 2. 재귀 3. 유클리드 호제법 4. DFS 5. BFS 6. 추천 문제 7. 참고자료- Search란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정- 그래프 탐색 알고리즘으로 DFS/BFS가 있음 1. 스택과 큐Stack- FILO(First In Last Out)의 자료구조- 입구와 출구가 동일stack = []# 삽입stack.append(val)# 삭제stack.pop()# 최상단 원소 확인print(stack[-1])Queue- FIFO(First In First Out)의 자료구조- 입구와 출구가 양쪽으로 나있는 터널 형태queue = []# 삽입queue.append(val)# 삭제queue.pop(0)# 최하단/최상단 원소 확인queue[0]queue[-1.. 2024. 7. 19. 이전 1 다음 반응형
