Name: Ashutosh Kumar Reg.
Num: 231070006 Batch: A
AI LAB Experiment 1
Aim: Implement Breadth first and depth first search techniques.
Theory:
Breadth-First Search (BFS) and Depth-First Search (DFS) are graph traversal
algorithms used
to explore nodes in a graph or tree. BFS:
Strategy: Explores nodes level by level, using a queue.
Key Feature: Finds the shortest path in an unweighted graph.
Applications: Shortest path in unweighted graphs, level-order traversal in trees.
DFS:
Strategy: Explores as deep as possible along a branch before backtracking, using
a stack (or
recursion).
Key Feature: May not find the shortest path but explores all paths deeply.
Applications: Pathfinding, solving puzzles, topological sorting.
Code:
DFS:
#include <iostream>
using namespace std;
// Binary Tree Node class
class Node {
public:
int value;
Node* left;
Node* right;
Node(int val) {
value = val;
left = right = nullptr;
}
};
// Preorder DFS traversal function (Root -> Left -> Right)
void preorder(Node* root) {
if (root == nullptr) return;
cout << root->value << " "; // Process the root
preorder(root->left); // Recurse on left child
preorder(root->right); // Recurse on right child
}
1|Page
Name: Ashutosh Kumar Reg. Num: 231070006 Batch: A
// Inorder DFS traversal function (Left -> Root -> Right)
void inorder(Node* root) {
if (root == nullptr) return;
inorder(root->left); // Recurse on left child
cout << root->value << " "; // Process the root
inorder(root->right); // Recurse on right child
}
// Postorder DFS traversal function (Left -> Right -> Root)
void postorder(Node* root) {
if (root == nullptr) return;
postorder(root->left); // Recurse on left child
postorder(root->right); // Recurse on right child
cout << root->value << " "; // Process the root
}
// Driver code
int main() {
// Creating the binary tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Perform DFS traversals on the tree
cout << "DFS Preorder Traversal: ";
preorder(root);
cout << endl;
cout << "DFS Inorder Traversal: ";
inorder(root);
cout << endl;
cout << "DFS Postorder Traversal: ";
postorder(root);
cout << endl;
return 0
OutPut
2|Page
Name: Ashutosh Kumar Reg. Num: 231070006 Batch: A
BFS:
#include <iostream>
#include <queue>
using namespace std;
// Binary Tree Node class
class Node {
public:
int value;
Node* left;
Node* right;
Node(int val) {
value = val;
left = right = nullptr;
}
};
// BFS traversal function (Level Order Traversal)
void bfs(Node* root) {
if (root == nullptr) return;
queue<Node*> q;
q.push(root); // Enqueue root
while (!q.empty()) {
Node* node = q.front(); // Dequeue
q.pop();
cout << node->value << " "; // Process the current node
// Enqueue left and right children
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
// Driver code
int main() {
// Creating the binary tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Perform BFS on the tree
3|Page
Name: Ashutosh Kumar Reg. Num: 231070006 Batch: A
cout << "BFS (Level Order Traversal): ";
bfs(root);
cout << endl;
return 0;
}
Output:
Conclusion :
BFS (Breadth-First Search) explores the graph level by level, making it ideal for
finding the shortest path in
unweighted graphs. It uses a queue and is more memory-intensive for wide
graphs.
DFS (Depth-First Search) explores the graph by going
deep into one branch before backtracking, making it suitable
4|Page
Name: Ashutosh Kumar Reg. Num: 231070006 Batch: A
for tasks like cycle detection and topological sorting. It
uses a stack or recursion and is more memory-efficient for
deep or sparse graphs.
Both algorithms have a time complexity of O(V + E), but their
memory usage and traversal order differ. BFS guarantees shorter
paths, while DFS is better for exhaustive exploration.
5|Page
