DFS Depth-Frist Search
- 현재 분기를 완벽하게 탐색한 뒤 다음 분기로 이동
- 현재 노드와 인접한 노드를 우선 탐색
- 더 이상 인접한 노드기 없을 때까지 반복
- 그래프 내에 cycle 여부를 확인할 때 사용
// Binary Tree에서의 DFS
struct Node
{
int value;
Node *left, *right;
}
// 어떤 binary tree의 root
// tree를 구성하고 있다고 가정
Node* root = ...;
stack<Ndoe*> s;
s.push(root);
// q가 빌 때까지 반복
while (!s.empty())
{
// 현재 pop 삭제
Node* current = s.top();
cout << current->value << "\n";
// 현재 노드 삭제
s.pop();
// child를 q에 추가
if (current->right) s.push(current->right);
if (current->left) s.push(current->left);
}
BFS Breadth-Frist Search
- 첫 노드와 인접한 모든 노드를 우선 탐색
- Sibling 노드들을 우선 탐색한 뒤 그들의 Child로 이동
- 두 노드 사이의 최단경로를 탐색할 때 사용
// Binary Tree에서의 BFS
struct Node
{
int value;
Node *left, *right;
}
// 어떤 binary tree의 root
// tree를 구성하고 있다고 가정
Node* root = ...;
queue<Node*> q;
q.push(root);
// q가 빌 때까지 반복
while (!q.empty())
{
// 현재 노드 할당받아 처리
Node* current = q.front();
cout << current->value << "\n";
// 현재 노드 삭제
q.pop();
// child를 q에 추가
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
출처
