Uninformed Search
Algorithms (BFS and
DFS)
Introduction to Artificial Intelligence
What is Uninformed Search
Algorithms:
Uninformed Search Algorithms are also called blind search algorithms.
• These algorithms search for a solution without any prior knowledge about the
problem domain.
• They only use the information provided in the problem, such as the initial
state, possible actions, and goal state.
The most common uninformed search algorithms are:
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Both are used for traversing graphs or trees to find a solution.
Breadth-First Search (BFS)
• BFS is a level-order traversal algorithm.
• It explores all the nodes at the current depth level before moving to
the next level.
• BFS uses a queue (FIFO) data structure to keep track of nodes to visit.
WORKING OF BFS:
• Start at the root node (or initial node).
• Visit all neighboring nodes (children) at the current level.
• Move to the next level and repeat until all nodes are visited or the goal node
is found.
Example
Level 0 A
Level 1 B C
Level 2 D E F G
• Start from node A.
• Explore the children B and C (Level 1).
• Explore the children of B → D and E, and the child of C → F and G
(Level 2).
IMPLEMENTATION OF BFS
Start with node A → add neighbors B and C to the queue.
Visit node B → add neighbors D and E to the queue.
Visit node C → add neighbor F to the queue.
Visit D, E, and F.
Depth-First Search (DFS)
• DFS is a depth-based traversal algorithm.
• It explores as far as possible down a branch before backtracking.
• DFS uses a stack (LIFO), either explicitly or through recursion.
WORKING OF DFS:
• Start at the root node.
• Visit the first child and move deeper into the tree/graph.
• Backtrack when no more nodes are available and continue exploring other
branches.
Example
Level 0 A
Level 1 B C
Level 2 D E F G
• Start at A.
• Explore B → D → backtrack to B → E.
• Backtrack to A → C → F backtrack to C → G.
IMPLEMENTATION OF BFS
Start with node A → add neighbors B and then D to the
queue. After that backtrack to B and Add E.
Visit node B again then backtrack to A, then add neighbors
C and E to the queue.
Then Visit back to node C → add neighbor G to the queue.
