BFS Solutions
1. Implement Breadth-First Search
import collections
def bfs(graph, start_node):
"""
Performs BFS on a graph represented as an adjacency list.
Args:
graph (dict): The graph as an adjacency list.
start_node: The node to start the traversal from.
Returns:
list: A list of nodes in the order they were visited.
"""
if start_node not in graph:
return []
visited = set()
queue = collections.deque([start_node])
visited.add(start_node)
traversal_order = []
while queue:
# Dequeue a vertex from the front of the queue
current_node = queue.popleft()
traversal_order.append(current_node)
# Get all adjacent vertices of the dequeued vertex.
# If an adjacent has not been visited, then mark it
# visited and enqueue it.
for neighbor in graph.get(current_node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return traversal_order
# Example Usage:
graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}
print(f"BFS Traversal: {bfs(graph, 'A')}")
# Expected Output: ['A', 'B', 'C', 'D', 'E', 'F']
2. Shortest Path in a Grid
import collections
def shortest_path_grid(grid):
"""
Finds the shortest path in a binary grid from (0,0) to (n-1, n-1).
"""
n = len(grid)
# If start or end is an obstacle, no path is possible.
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
# 8 possible directions
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
# Queue stores (row, col, path_length)
queue = collections.deque([(0, 0, 1)])
visited = set([(0, 0)])
while queue:
row, col, length = queue.popleft()
# If we reached the destination
if row == n - 1 and col == n - 1:
return length
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# Check if the new position is valid
if (0 <= new_row < n and
0 <= new_col < n and
grid[new_row][new_col] == 0 and
(new_row, new_col) not in visited):
visited.add((new_row, new_col))
queue.append((new_row, new_col, length + 1))
# If the queue becomes empty and we haven't reached the end
return -1
# Example Usage:
grid = [[0,0,0],[1,1,0],[1,1,0]]
print(f"Shortest Path Length: {shortest_path_grid(grid)}")
# Expected Output: 4
DFS Solutions
3. Implement Depth-First Search
def dfs(graph, start_node):
"""
Performs DFS on a graph using recursion.
"""
if start_node not in graph:
return []
visited = set()
traversal_order = []
def _dfs_recursive(node):
# If node is already visited, do nothing
if node in visited:
return
# Mark the current node as visited and add to result
visited.add(node)
traversal_order.append(node)
# Recur for all the vertices adjacent to this vertex
for neighbor in graph.get(node, []):
_dfs_recursive(neighbor)
_dfs_recursive(start_node)
return traversal_order
# Example Usage:
graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}
print(f"DFS Traversal: {dfs(graph, 'A')}")
# Expected Output: ['A', 'B', 'D', 'E', 'F', 'C'] (Note: Order can vary)
4. Connected Components in a Network
def count_components(isConnected):
"""
Counts the number of connected components in a network
represented by an adjacency matrix.
"""
n = len(isConnected)
visited = set()
component_count = 0
def _dfs(start_node):
# Use a stack for iterative DFS to avoid recursion depth issues
stack = [start_node]
while stack:
node = stack.pop()
# Find all connected neighbors
for neighbor in range(n):
if isConnected[node][neighbor] == 1 and neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
# Iterate through all computers
for i in range(n):
# If we find a computer that hasn't been visited,
# it's the start of a new component.
if i not in visited:
component_count += 1
visited.add(i)
# Start DFS to find all computers in this component
_dfs(i)
return component_count
# Example Usage:
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
print(f"Number of Components: {count_components(isConnected)}")
# Expected Output: 2
Data Analysis Solution
5. Analysis of the Iris Dataset
import pandas as pd
def analyze_iris():
"""
Performs the requested analysis on the Iris dataset.
"""
try:
# 1. Load Data
url = 'https://raw.githubusercontent.com/mwaskom/seaborn-data/master/iris.csv'
df = pd.read_csv(url)
print("--- 1. Data Loaded Successfully (First 5 Rows) ---")
print(df.head())
print("\\n" + "="*50 + "\\n")
# 2. Grouped Analysis
print("--- 2. Average Petal Length by Species ---")
avg_petal_length = df.groupby('species')['petal_length'].mean()
print(avg_petal_length)
print("\\n" + "="*50 + "\\n")
# 3. Filtering
print("--- 3. Virginica Species with Sepal Width > 3.5 ---")
filtered_df = df[(df['species'] == 'virginica') & (df['sepal_width'] > 3.5)]
print(filtered_df)
except Exception as e:
print(f"An error occurred: {e}")
# Run the analysis
analyze_iris()