Notes

def depth_first_search(graph, start, goal):
# Stack holds (current_node, path_to_node)
stack = [(start, [start])]
visited = set()

while stack:
node, path = stack.pop()

if node == goal:
return path

if node not in visited:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
stack.append((neighbor, path + [neighbor]))

return None


graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

path = depth_first_search(graph, 'A', 'F')
print("DFS Path from A to F:", path)

2)
from collections import deque

def bfs(graph, start, goal):
# Queue holds (current_node, path_to_node)
frontier = deque([(start, [start])])
visited = set()

while frontier:
node, path = frontier.popleft()

if node == goal:
return path # return full path from start → goal

visited.add(node)

for neighbor in graph.get(node, []):
if neighbor not in visited:
frontier.append((neighbor, path + [neighbor]))

return None


# graph (undirected)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

path = bfs(graph, 'A', 'F')
print("Path from A to F:", path)
3)
import heapq

graph = {
'A': {'B': 4, 'C': 2},
'B': {'D': 3, 'E': 5},
'C': {'E': 8},
'D': {'G': 1},
'E': {'G': 2},
'G': {}
}

h = {'A': 10, 'B': 6, 'C': 7, 'D': 3, 'E': 2, 'G': 0}

def a_star_search(graph, start, goal, h):
# Priority queue: (f = g + h, g, node, path)
pq = [(h[start], 0, start, [start])]
visited = set()

while pq:
f, g, node, path = heapq.heappop(pq)

if node in visited:
continue
visited.add(node)

if node == goal:
return path, g

for neighbor, cost in graph[node].items():
if neighbor not in visited:
new_g = g + cost
new_f = new_g + h[neighbor]
heapq.heappush(pq, (new_f, new_g, neighbor, path + [neighbor]))

return None, float('inf')


path, total_cost = a_star_search(graph, 'A', 'G', h)

print("Path:", path)
print("Total cost:", total_cost)
4)
import heapq

graph = {
'A': {'B': 4, 'C': 2},
'B': {'D': 3, 'E': 5},
'C': {'E': 8},
'D': {'G': 1},
'E': {'G': 2},
'G': {}
}

def uniform_cost_search(graph, start, goal):
# Priority queue: (cost, node, path)
pq = [(0, start, [start])]
visited = set()

while pq:
cost, node, path = heapq.heappop(pq)

if node in visited:
continue
visited.add(node)

if node == goal:
return path, cost

for neighbor, edge_cost in graph[node].items():
if neighbor not in visited:
heapq.heappush(pq, (cost + edge_cost, neighbor, path + [neighbor]))

return None, float('inf')


path, total_cost = uniform_cost_search(graph, 'A', 'G')

print("Path:", path)
print("Total cost:", total_cost)