Name Kush Kiran Nhayade

UID no. 2022300068

Experiment No. 2

DFS

PROGRAM: from collections import defaultdict

class Map:
def init (self, nodes):
self.nodes_count = nodes
self.edges = defaultdict(list)

def connect_nodes(self, node_a, node_b, distance):

self.edges[node_a].append((node_b, distance))
self.edges[node_b].append((node_a, distance))

def depth_first_search(self, start_point, destination):

if start_point not in self.edges or destination not in self.edges:
print(f"One or both nodes '{start_point}' and '{destination}' are not
in the graph.")
return

explored = set()
node_stack = [(start_point, 0)]
route_parent = {start_point: None}
total_cost = {start_point: 0}

while node_stack:
current_node, cumulative_cost = node_stack.pop()

if current_node in explored:
continue

explored.add(current_node)
print(f"Visited: {current_node}, Cost from start: {cumulative_cost}")

if current_node == destination:
break
 for neighbor, path_cost in reversed(self.edges[current_node]):
if neighbor not in explored:
node_stack.append((neighbor, cumulative_cost + path_cost))
route_parent[neighbor] = current_node
total_cost[neighbor] = cumulative_cost + path_cost

route = []
if destination in route_parent:
step = destination
while step is not None:
route.append(step)
step = route_parent[step]
route.reverse()

if route:
total_path_cost = total_cost[destination]
print("Path from", start_point, "to", destination, ":", " ->
".join(route))
print("Total cost from start to end:", total_path_cost)
else:
print("No path found from", start_point, "to", destination)

# Example usage
m = Map(20)

m.connect_nodes('Oradea', 'Zerind', 71)

m.connect_nodes('Oradea', 'Sibiu', 151)
m.connect_nodes('Zerind', 'Arad', 75)
m.connect_nodes('Arad', 'Sibiu', 140)
m.connect_nodes('Arad', 'Timisoara', 118)
m.connect_nodes('Timisoara', 'Lugoj', 111)
m.connect_nodes('Lugoj', 'Mehadia', 70)
m.connect_nodes('Mehadia', 'Drobeta', 75)
m.connect_nodes('Drobeta', 'Craiova', 120)
m.connect_nodes('Craiova', 'Rimnicu Vilcea', 146)
m.connect_nodes('Rimnicu Vilcea', 'Sibiu', 80)
m.connect_nodes('Rimnicu Vilcea', 'Pitesti', 97)
m.connect_nodes('Pitesti', 'Craiova', 138)
m.connect_nodes('Pitesti', 'Bucharest', 101)
m.connect_nodes('Sibiu', 'Fagaras', 99)
m.connect_nodes('Fagaras', 'Bucharest', 211)
m.connect_nodes('Bucharest', 'Giurgiu', 90)
m.connect_nodes('Bucharest', 'Urziceni', 85)
m.connect_nodes('Urziceni', 'Hirsova', 98)
 m.connect_nodes('Hirsova', 'Eforie', 86)
m.connect_nodes('Urziceni', 'Vaslui', 142)
m.connect_nodes('Vaslui', 'Iasi', 92)
m.connect_nodes('Iasi', 'Neamt', 87)

m.depth_first_search('Oradea', 'Bucharest')

RESULT:

BFS

PROGRAM:

from collections import defaultdict, deque

class MapTraversal:
def init (self, nodes):
self.node_count = nodes
self.connections = defaultdict(list)

def connect_locations(self, loc_a, loc_b, distance):

self.connections[loc_a].append((loc_b, distance))
self.connections[loc_b].append((loc_a, distance))

def breadth_first_search(self, start_point, destination):

if start_point not in self.connections or destination not in
self.connections:
print(f"One or both locations '{start_point}' and '{destination}' are
not in the graph.")
return
 explored = set()
loc_queue = deque([(start_point, 0)])
explored.add(start_point)

route_parent = {start_point: None}

total_cost = {start_point: 0}

while loc_queue:
current_location, cumulative_cost = loc_queue.popleft()

print(f"Visited: {current_location}, Cost from start:

{cumulative_cost}")

if current_location == destination:
break

for neighbor, path_cost in self.connections[current_location]:

if neighbor not in explored:
explored.add(neighbor)
loc_queue.append((neighbor, cumulative_cost + path_cost))
route_parent[neighbor] = current_location
total_cost[neighbor] = cumulative_cost + path_cost

route = []
if destination in route_parent:
step = destination
while step is not None:
route.append(step)
step = route_parent[step]
route.reverse()

if route:
total_path_cost = total_cost[destination]
print("Path from", start_point, "to", destination, ":", " ->
".join(route))
print("Total cost from start to end:", total_path_cost)
else:
print("No path found from", start_point, "to", destination)

# Example usage
m = MapTraversal(20)

m.connect_locations('Oradea', 'Zerind', 71)

m.connect_locations('Oradea', 'Sibiu', 151)
m.connect_locations('Zerind', 'Arad', 75)
m.connect_locations('Arad', 'Sibiu', 140)
m.connect_locations('Arad', 'Timisoara', 118)
m.connect_locations('Timisoara', 'Lugoj', 111)
m.connect_locations('Lugoj', 'Mehadia', 70)
m.connect_locations('Mehadia', 'Drobeta', 75)
m.connect_locations('Drobeta', 'Craiova', 120)
m.connect_locations('Craiova', 'Rimnicu Vilcea', 146)
m.connect_locations('Rimnicu Vilcea', 'Sibiu', 80)
m.connect_locations('Rimnicu Vilcea', 'Pitesti', 97)
m.connect_locations('Pitesti', 'Craiova', 138)
m.connect_locations('Pitesti', 'Bucharest', 101)
m.connect_locations('Sibiu', 'Fagaras', 99)
m.connect_locations('Fagaras', 'Bucharest', 211)
m.connect_locations('Bucharest', 'Giurgiu', 90)
m.connect_locations('Bucharest', 'Urziceni', 85)
m.connect_locations('Urziceni', 'Hirsova', 98)
m.connect_locations('Hirsova', 'Eforie', 86)
m.connect_locations('Urziceni', 'Vaslui', 142)
m.connect_locations('Vaslui', 'Iasi', 92)
m.connect_locations('Iasi', 'Neamt', 87)

m.breadth_first_search('Oradea', 'Bucharest')
w
RESULT:

BFS (Breadth-First Search):

Completeness: BFS will always find a solution if one exists because it explores each level of the graph before
moving on to the next.
Optimality: In unweighted graphs, BFS finds the shortest path between the start and goal nodes.
Time Complexity: BFS has a time complexity of O(V + E), where V is the number of vertices (nodes), and E is
the number of edges (connections). It checks every node and connection.
Space Complexity: BFS uses O(V) space, as it needs to store all nodes at the current level, which can be large for
wide graphs.

DFS (Depth-First Search):

Completeness: DFS might not always find a solution unless you track visited nodes to avoid infinite loops.
Optimality: DFS is usually not optimal; it might not find the shortest path as it goes deep into each branch
before backtracking.
Time Complexity: DFS has a time complexity of O(V + E), similar to BFS, since it explores every node and edge.
Space Complexity: DFS's space complexity can vary. In the worst case, it’s O(V), but it can be more memory-
efficient than BFS in some cases, especially in graphs with fewer connections.
CONCLUSION: The DFS and BFS methods both explore paths in a graph by visiting connected nodes.
DFS digs deep into one path before going back, while BFS looks at all nearby nodes first before moving
further. Both methods help find the shortest path and total cost between two points.