DFS3 그래프 탐색 - 너비 우선 탐색(BFS) DFS는 스택을 사용해서 구현했었다BFS는 큐를 사용한다!! 큐는 들어간 순서대로 나오는 거 FIFO 1) 큐가 비었나 확인(비었으면 모든 노드 다 방문한 거임. 탐색종료)2) 큐에서 노드를 팝3) 방금 막 팝한 노드 인접 노드 확인-> 그 중 방문 안한거 있으면 그 노드 큐에 푸쉬 후 방문 처리 1. 그림으로 보는 큐를 이용한 DFS 2. 코드로 보는 큐로 구현한 DFS#include #include #include #include using namespace std;// 인접 리스트vector> AdjList;// 방문 여부vector bVisited;// BFS 함수void BFS(int StartNode){ queue Q; Q.push(StartNode); bVisite.. 2025. 2. 5. 그래프 탐색 - 깊이 우선 탐색 DFS DFS는 스택 or 재귀 이용해서 푼다1. 스택을 활용한 DFS탐색 전 시작 노드 정하기스택에 시작 노드를 Push스택에 있는 노드는 방문 안 한 노드 && 방문 예정 노드임스택이 비었는지 확인-> 비었으면 모두 방문한거니까 탐색 종료스택에서 노드 팝-> 팝한 원소는 최근 스택에 푸시한 노드팝한 노드의 방문 여부 확인-> 안했으면 방문방문한 노드와 인접 모든 노드 확인-> 안 했으면 노드를 스택에 푸시 1.1. 그림으로 보는 스택으로 만드는 DFS 1.2. 코드로 구현한 DFSsort함수 쓰려고 algorithm 추가했당. #include #include #include #include using namespace std;// 인접 리스트vector> AdjList;// 방문 여부vector bVisit.. 2025. 2. 4. [자료구조] DFS와 BFS DFS 와 BFS란?DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 탐색 알고리즘그래프의 모든 노드를 탐색하는 방법임두 알고리즘은 탐색의 순서와 방식에서 차이 있음시간복잡도는 DFS/ BFS 동일함-> 왜냐? 모든 조건 내 모든 노드를 검색하니까--> But, 최단거리 구할 때는 BFS가 유리함 1. DFS (Depth-First Search)- 개념: DFS는 깊이 우선 탐색한 노드에서 시작하여 다음 분기로 넘어가기 전에!!해당 분기를 따라 최대한 깊이 내려가며 탐색하는 방법 - 특징: 스택 (Stack) 사용재귀 호출을 사용할 수 있음한 경로를 끝까지 탐색한 후, 다른 경로를 탐색 2. BFS (Breadth-First Search)- 개념:BF.. 2024. 8. 2. 이전 1 다음
