Submission Date : 19th March 2024 Course Teacher’s Name : Md Naimul Pathan
Lab Report Status
Marks: ………………………………… Signature:..................... Comments:.............................................. Date:.............................. TITLE OF THE LAB REPORT EXPERIMENT Demonstrate and code BFS. OBJECTIVES/AIM • To attain knowledge on the Collab and how it works. • To gather knowledge on BFS for beginners.. • To implement the basics of Python.
PROCEDURE / ANALYSIS / DESIGN Else:
DFS is an algorithm used for traversing or searching tree or graph data structures. It explores as far as possible along each branch before backtracking. • Start with the chosen starting vertex. • Mark the starting vertex as visited. • Visit the current vertex and process it. • Explore all unvisited neighboring vertices of the current vertex recursively or iteratively. For each unvisited neighboring vertex, mark it as visited and recursively apply the DFS procedure on it.If there are no unvisited neighboring vertices, backtrack to the previous vertex. IMPLEMENTATION : graph = { 'A' : ['B','F','I'], 'B' : ['A','C', 'E'], 'C' : ['B','D','E'], 'D' : ['C','G','H'], 'E' : ['B','C','G'], 'F' : ['A','G'], 'G' : ['D','E','F'], 'H' : ['D'], 'I' : ['A'] }
visited = [] queue = []
def bfs(visited, graph, node): #function for BFSs
visited.append(node) queue.append(node)
while queue: # Creating loop to visit each node
m = queue.pop(0) print (m, end = " ")
for neighbour in graph[m]:
if neighbour not in visited: visited.append(neighbour) queue.append(neighbour)
# Driver Code print("Following is the Breadth-First Search") bfs(visited, graph, 'A') # function calling
Result:
ANALYSIS AND DISCUSSION:
Breadth-First Search is an algorithm used for traversing or searching tree or graph data structures. It starts at a chosen vertex (or node) of a graph and explores all of the neighboring vertices at the current depth before moving to the vertices at the next depth level. SUMMARY BFS is a widely used graph traversal algorithm that explores all the nodes reachable from a given source node in the shortest path order. It starts at the source node, explores its neighbors, and then moves to the next level of neighbors until all nodes are visited. The use of a queue ensures that nodes are visited in the order they are discovered, resulting in a level-by-level traversal. This algorithm is particularly useful for finding shortest paths in unweighted graphs and for exploring nodes in a hierarchical structure.
Lab Report NO #02
TITLE OF THE LAB REPORT EXPERIMENT: DFS demonstration and Code. OBJECTIVES/AIM • To attain knowledge on the Colab and how it works. • To gather knowledge of basic DFS for beginners. • To implement the basic DFS and adjacency list. PROCEDURE / ANALYSIS / DESIGN We define a Graph class to represent the graph structure. The graph is implemented using an adjacency list. The add_edge method is used to add edges to the graph. It takes two vertices u and v and adds an edge from u to v. The dfs_util method is a recursive utility function that performs the DFS traversal starting from a given vertex. It takes the current vertex and a set of visited vertices as parameters. It marks the current vertex as visited, prints it, and then recursively calls itself on all unvisited neighbors of the current vertex. The dfs method is the entry point for the DFS traversal. It initializes an empty set to keep track of visited vertices and then calls dfs_util with the starting vertex. In the example usage, we create a Graph object and add some edges to it. Then, we call the dfs method to perform DFS traversal starting from vertex 2. Implementation: graph = { 'A' : ['B','F','I'], 'B' : ['A','C', 'E'], 'C' : ['B','D','E'], 'D' : ['C','G','H'], 'E' : ['B','C','G'], 'F' : ['A','G'], 'G' : ['D','E','F'], 'H' : ['D'], 'I' : ['A'] }
visited = [] queue = []
def bfs(visited, graph, node): #function for BFSs
visited.append(node) queue.append(node)
while queue: # Creating loop to visit each node
m = queue.pop() print (m, end = " ")
for neighbour in graph[m]:
if neighbour not in visited: visited.append(neighbour) queue.append(neighbour)
# Driver Code print("Following is the Breadth-First Search") bfs(visited, graph, 'A') # function calling
Output:
ANALYSIS AND DISCUSSION:
Depth-First Search (DFS) is a fundamental graph traversal algorithm used to explore vertices and edges in a graph structure. It traverses as far as possible along each branch before backtracking. This approach is often implemented using a stack data structure or recursion.
SUMMARY Depth-first search (DFS) is a graph traversal algorithm used to explore a graph or tree data structure. DFS is a powerful algorithm for traversing or searching graph or tree structures.
