In this assignment, you will implement two fundamental graph searching algorithms: Depth$-$First Search $($DFS$)$ and Breadth$-$First Search $($BFS$).$ You will use Python and Google Colab as your development environment.

Instructions

Graph Representation:

Create an undirected graph using an adjacency list. You can represent the graph as a dictionary where keys are node identifiers, and values are lists of adjacent nodes.

Implement Depth$-$First Search $($DFS$)$:

Write a function dfs$($graph$,$ start$)$ that performs DFS on the graph starting from the start node.

The function should return a list of nodes in the order they are visited.

Implement Breadth$-$First Search $($BFS$)$:

Write a function bfs$($graph$,$ start$)$ that performs BFS on the graph starting from the start node.

The function should return a list of nodes in the order they are visited.

Graph Visualization:

Write a function visualize$\_$graph$($graph$)$ to visualize the graph using networkx and matplotlib.

Testing the Algorithms:

Create a sample graph and test both DFS and BFS functions.

Display the graph and the order of node visits for both algorithms.

Sample Code Structure:

import networkx as nx

import matplotlib.pyplot as plt

# Function to visualize the graph

def visualize$\_$graph$($graph$)$:

G $=$ nx$.$Graph$($graph$)$

pos $=$ nx$.$spring$\_$layout$($G$)$

nx$.$draw$($G$,$ pos, with$\_$labels$=$True, node$\_$color$=$'lightblue', edge$\_$color$=$'gray', node$\_$size$=2000,$ font$\_$size$=20)$

plt$.$show$()$

# Depth$-$First Search $($DFS$)$ implementation

def dfs$($graph$,$ start$)$:

visited $=$ set$()$

stack $=[$start$]$

visit$\_$order $=[]$

while stack:

node $=$ stack.pop$()$

if node not in visited:

visited.add$($node$)$

visit$\_$order.append$($node$)$

stack.extend$($reversed$($graph$[$node$]))$ # Add adjacent nodes in reverse order for consistent traversal

return visit$\_$order

# Breadth$-$First Search $($BFS$)$ implementation

def bfs$($graph$,$ start$)$:

visited $=$ set$()$

queue $=[$start$]$

visit$\_$order $=[]$

while queue:

node $=$ queue.pop$(0)$

if node not in visited:

visited.add$($node$)$

visit$\_$order.append$($node$)$

queue.extend$($graph$[$node$])$ # Add adjacent nodes

return visit$\_$order

# Sample graph represented as an adjacency list

graph $=\{$

$\text{'}$A$\text{'}$: $[\text{'}$B$\text{'},\text{'}$C$\text{'}],$

$\text{'}$B$\text{'}$: $[\text{'}$A$\text{'},\text{'}$D$\text{'},\text{'}$E$\text{'}],$

$\text{'}$C$\text{'}$: $[\text{'}$A$\text{'},\text{'}$F$\text{'}],$

$\text{'}$D$\text{'}$: $[\text{'}$B$\text{'}],$

$\text{'}$E$\text{'}$: $[\text{'}$B$\text{'},\text{'}$F$\text{'}],$

$\text{'}$F$\text{'}$: $[\text{'}$C$\text{'},\text{'}$E$\text{'}]$

$\}$

# Visualize the graph

visualize$\_$graph$($graph$)$

# Test DFS and BFS

dfs$\_$result $=$ dfs$($graph$,\text{'}$A$\text{'})$

bfs$\_$result $=$ bfs$($graph$,\text{'}$A$\text{'})$

print$($f$"$DFS Visit Order: $\{$dfs$\_$result$\}")$

print$($f$"$BFS Visit Order: $\{$bfs$\_$result$\}")$