DEPTH FIRST SEARCH

Ex No: 2      Implementation of Uninformed search algorithms (DFS) 

CLICK HERE PROGRAM LINK

 -------------------------------------------------------------------------------------------------------------

NOTE:

DFS - Uninformed Search (Blind Search)

Uninformed search algorithms don't have additional information about the problem, except for the structure of the problem itself. They explore the search space based on the current state, without using any specific knowledge or heuristics to guide the search.

Pros:

• Simplicity: Easy to implement.
• Completeness: Guaranteed to find a solution (if one exists) in some cases (like BFS or Uniform Cost Search).

Cons:

• Inefficiency: May explore large parts of the search space unnecessarily.
• High memory consumption or slow processing in some cases (e.g., DFS).

         -------------------------------------------------------------------------------------------------------------

Aim

The aim of implementing  Depth-First Search (DFS) algorithms is to traverse a graph or a tree data structure in a systematic way, visiting all nodes and edges in the structure in a particular order, without revisiting any node twice.

Algorithm

Depth-First Search (DFS) algorithm:

1. Mark the starting node as visited and print it

2. For each adjacent node of the current node that has not been visited, repeat step 1

3. If all adjacent nodes have been visited, backtrack to the previous node and repeat step 2

4. Repeat steps 2-3 until all nodes have been visited

PROGRAM:

# Define the graph

graph = {

    '5' : ['3', '7'],

    '3' : ['2', '4'],

    '7' : ['8'],

    '2' : [],

    '4' : ['8'],

    '8' : []

}

visited = set()  # Set to keep track of visited nodes of the graph

# Function for DFS

def dfs(visited, graph, node):

    if node not in visited:

        print(node, end=" ")  # Print the node

        visited.add(node)      # Mark the node as visited

        for neighbour in graph[node]:

            dfs(visited, graph, neighbour)  # Recursively visit the neighbors

# Driver Code

print("Following is the Depth-First Search:")

dfs(visited, graph, '5')

o/p

DFS

Following is the Depth-First Search

5

3

2

4

8

7

Result

Thus the program for BFS and DFS is executed successfully and output is verified