[go: up one dir, main page]
Scribd
Upload
89 views4 pages

Green University of Bangladesh Department of Computer Science and Engineering (CSE)

This lab report describes implementing a depth-first search (DFS) algorithm using Python. The document includes: 1) An analysis of the DFS algorithm, which starts at the root node and explores branches as far as possible before backtracking. 2) The Python implementation, which uses a recursive function to add the current node as visited, traverse unvisited neighbors recursively, and print visited nodes. 3) A test of the algorithm by inputting a starting node and edges between nodes to perform DFS traversal and output the results.

Uploaded by

Mafuj Ahmed Bishal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
89 views4 pages

Green University of Bangladesh Department of Computer Science and Engineering (CSE)

This lab report describes implementing a depth-first search (DFS) algorithm using Python. The document includes: 1) An analysis of the DFS algorithm, which starts at the root node and explores branches as far as possible before backtracking. 2) The Python implementation, which uses a recursive function to add the current node as visited, traverse unvisited neighbors recursively, and print visited nodes. 3) A test of the algorithm by inputting a starting node and edges between nodes to perform DFS traversal and output the results.

Uploaded by

Mafuj Ahmed Bishal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Green University of Bangladesh

Department of Computer Science and Engineering


(CSE)
Faculty of Sciences and Engineering
Semester: (Fall, Year:2022), B.Sc. in CSE (Day/Eve)

LAB REPORT NO 02
Course Title: Artificial intelligence Lab
Course Code: CSE316 Section: D14

Lab Experiment Name: Implement DFS algorithm using Python

Student Details

Name ID

1. Mafuj Ahmed Bishal 201002158

Lab Date : 29 October 2022


Submission Date : 29 October 2022
Course Teacher’s Name : Hasan Muhammad

[For Teachers use only: Don’t Write Anything inside this box]

Lab Report Status


Marks: ………………………………… Signature: .....................
Comments: .............................................. Date: ..............................
1. TITLE

Implement BFS algorithm using Python

2. PROBLEM ANALYSIS

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The
algorithm starts at the root node and explores as far as possible along each branch before backtracking.

In here for DFS basic algorithm is:


• Create recursive function that takes node and visited array.
• Add current as visited
• Traverse all the unvisited node using recursive function call.

3. IMPLEMENTATION

• Code:

from collections import defaultdict


class Graph:
def __init__(self):
self.graph = defaultdict(list)

def Add_The_Edge(self, u, v):


self.graph[u].append(v)

def Dfs_Function(self, v, visited):

visited.add(v)
print(v)

for i in self.graph[v]:
if i not in visited:
self.Dfs_Function(i, visited)

def Dfs_Traversal(self, v):


visited = set()
self.Dfs_Function(v, visited)

if __name__ == "__main__":
graph = Graph()
starting_node = int(input("Enter the starting node: "))
print(" ")
number_of_edges = int(input("Enter the number of edges: "))
for i in range(number_of_edges):
print(" ")
print("This is Edge",i+1)
print(" ")
source = int(input("From: "))
connected_node = int(input("To: "))
graph.Add_The_Edge(source, connected_node)

graph.Dfs_Traversal(starting_node)

4. TEST

You might also like