aiml-lab-week4

Week4: uninformed search = BFS, DFS

PART-A: BFS

Part-B: DFS

Outcome of this week is:

Aim: To write a Python program for performing uninformed search strategies

why they are called so:

they operate without any additional domain-specific knowledge or heuristics to guide their search toward the goal state.

PART-A

DFS=?

Depth-First Search => explores as deep as possible along one branch before backtracking. Assume left child first.

A ---> B
B---> D
D--->leaf, back track to B (now move to the left over child) ---> E
E---> leaf , back track to B (already covered), back track to A (left over child in A is C)---> C
C---> F
F ---> leaf, C to A... covered all paths

The final traversal is A B D E C F

DFS

# DFS

from collections import deque

def dfs(graph, node, visited=None):

if visited is None:

visited = set()

visited.add(node)

print(node, end=" ")

for n in graph[node]:

if n not in visited:

dfs(graph, n, visited)

graph = {

'A': ['B', 'C'],

'B': ['D', 'E'],

'C': ['F'],

'D': [],

'E': [],

'F': []

}

bfs(graph, 'A')

BFS=?

Breadth-First Search => explores nodes level by level, starting from the source. Unlike DFS, BFS guarantees the shortest path in an unweighted graph.

Node(A) ---> Queue (B, C); Node(A) covered B, C nodes ---> dequeue(A) ---> Queue(B,C)
Node(B) ---> Queue (D, E); Node(B) covered D, E nodes; dequeue(B) ---> Queue(C, D, E)
Node(C)---> F; Node(C) covered F node; dequeue(C); Queue(D,E, F)
Node(D) ---> dequeue(D); Queue(E,F)
Node(E) ---> deuque(E); Queue(F)
Node(F)---> dequeue(F)...
all nodes covered

The final traversal is A B C D E F

BFS

# BFS

from collections import deque

def bfs(graph, start):

visited = set()

queue = deque([start])

visited.add(start)

while queue:

node = queue.popleft()

print(node, end=" ")

for neighbour in graph[node]:

if neighbour not in visited:

visited.add(neighbour)

queue.append(neighbour)

graph = {

'A': ['B', 'C'],

'B': ['D', 'E'],

'C': ['F'],

'D': [],

'E': [],

'F': []

}

bfs(graph, 'A')

Practice Graphs: (graphs-unweighted examples)

#graph1:

'A': ['B', 'D'],

'B': ['C'],

'C': ['E', 'F'],

'D': ['E'],

'E': ['H'],

'F': ['G'],

'G': [],

'H': []

#graph2:

'A': ['C'],

'B': ['A', 'D'],

'C': ['E', 'F'],

'D': ['G'],

'E': ['H'],

'F': [],

'G': [],

'H': []

#graph3:

'A': ['B', 'C'],

'B': ['E'],

'C': ['D', 'F'],

'D': ['G'],

'E': [],

'F': ['H'],

'G': [],

'H': []

Viva-voce Questions:

What is an uninformed search strategy in AI?
Uninformed search explores the search space without any domain-specific heuristic guidance. It uses only the problem’s structure. Examples include Breadth-First Search (BFS) and Depth-First Search (DFS).
Define Breadth-First Search (BFS).
BFS is a graph traversal algorithm that explores all nodes at the current depth before moving to the next level. It uses a FIFO queue to manage nodes.
Define Depth-First Search (DFS).
DFS is a graph traversal algorithm that explores as far along a branch as possible before backtracking. It uses a stack (or recursion) to keep track of nodes.
What data structure does BFS use and why?
BFS uses a queue because it ensures nodes are visited in the order they were discovered, maintaining level-by-level traversal.
What data structure does DFS use and why?
DFS uses a stack (explicit or via recursion) to explore deep paths first, backtracking when no further unvisited neighbours remain.
What is the time complexity of BFS and DFS?
For a graph with V vertices and E edges, both BFS and DFS have time complexity O(V + E) when using adjacency lists.
How does BFS handle the visited nodes during traversal?
BFS maintains a visited list or set to mark and avoid revisiting nodes already explored, preventing infinite loops.
How does DFS handle loops or cycles in a graph?
DFS keeps a visited set to ensure nodes are not revisited during recursion, preventing endless loops on cycles.
Give a real-world example where BFS is preferred over DFS.
BFS is preferred in finding the shortest path in unweighted networks, such as shortest communication paths in social networks.
Why would you implement both BFS and DFS in Python for uninformed search?
Implementing both demonstrates fundamental search strategies, shows traversal ordering differences, and illustrates how queue and stack behaviours impact exploration without heuristics.