Lab 04

Depth First Search

Objective:
This lab will introduce students to search problems. We will first start by representing problems in
terms of state space graph. Given a state space graph, starting state and a goal state, students will then
perform a basic Depth First Search solution within that graph. The output will be a set of actions or a
path that will begin from initial state/node and end in the goal node.

Activity Outcomes:
This lab teaches you the following topics:
How to represent problems in terms of state space graph
How to find a solution of those problems using Depth First Search.

Instructor Note:
As pre-lab activity, read Chapter 3 from the book (Artificial Intelligence, A Modern Approach by Peter
Norvig, 3rd edition) to know the basics of search algorithms.
1) Useful Concepts:
In the previous lab we studied breadth first search, which is the most naïve way of searching trees. The
path returned by breadth search is not optimal. Uniform cost search always returns the optimal path. In
this lab students will be able to implement a uniform cost search approach. Students will also be able to
apply depth first search to their problems

Depth First Search (DFS)

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive
searches of all the nodes by going ahead, if possible, else by backtracking.
Here, the word backtrack means that when you are moving forward and there are no more nodes along
the current path, you move backwards on the same path to find nodes to traverse. All the nodes wi ll be
visited on the current path till all the unvisited nodes have been traversed after which the next path will
be selected.
This recursive nature of DFS can be implemented using stacks. The basic idea is as follows:
Pick a starting node and push all its adjacent nodes into a stack. Pop a node from stack to select the
next node to visit and push all its adjacent nodes into a stack. Repeat this process until the stack is
empty. However, ensure that the nodes that are visited are marked. This will prevent y ou from visiting
the same node more than once. If you do not mark the nodes that are visited and you visit the same
node more than once, you may end up in an infinite loop.

Pseudocode

DFS-iterative (G, s): //Where G is graph and s is source vertex

let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited

DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)

The following image shows how DFS works.

 Figure 11 - Traversal

Time complexity O(V+E), when implemented using an adjacency list.

Applications
How to find connected components using DFS?
A graph is said to be disconnected if it is not connected, i.e. if two nodes exist in the graph such that
there is no edge in between those nodes. In an undirected graph, a connected component is a set of
vertices in a graph that are linked to each other by paths.
Consider the example given in the diagram. Graph G is a di sconnected graph and has the following 3
connected components.
First connected component is 1 -> 2 -> 3 as they are linked to each other
Second connected component 4 -> 5
Third connected component is vertex 6
In DFS, if we start from a start node it will mark all the nodes connected to the start node as visited.
Therefore, if we choose any node in a connected component and run DFS on that node it will mark the
whole connected component as visited.
 Figure 12 - Trvaersal

Input File
6
4
1 2
2 3
1 3
45
Code

#include <iostream>
#include <vector>
using namespace std;

vector <int> adj[10];

bool visited[10];

void dfs(int s) {
visited[s] = true;
for(int i = 0;i < adj[s].size();++i) {
if(visited[adj[s][i]] == false)
dfs(adj[s][i]);
}
}

void initialize() {
 for(int i = 0;i < 10;++i)
visited[i] = false;
}

int main() {
int nodes, edges, x, y, connectedComponents = 0;
cin >> nodes; //Number of nodes
cin >> edges; //Number of edges
for(int i = 0;i < edges;++i) {
cin >> x >> y;
//Undirected Graph
adj[x].push_back(y); //Edge from vertex x to vertex y
adj[y].push_back(x); //Edge from vertex y to vertex x
}

initialize(); //Initialize all nodes as not visited

for(int i = 1;i <= nodes;++i) {

if(visited[i] == false) {
dfs(i);
connectedComponents++;
}
}
cout << "Number of connected components: " << connectedComponents << endl;
return 0;
}

Output
Number of connected components: 3

2) Solved Lab Activities:

Sr.No Allocated Time Level of Complexity CLO Mapping

1 45 High CLO-6

Activity 1:
Consider a toy problem that can be represented as a following graph. How would you represent this
graph in python?
Solution:
Remember a node of a tree can be represented by four attributes. We consider node as a class having
four attributes namely,
1. State of the node
2. Parent of the node
3. Actions applicable to that node
4. The total path cost of that node starting f rom the initial state until that particular node is
reached

We can now implement this class in a dictionary. This dictionary will represent our state space graph.
As we will traverse through the graph, we will keep updating parent and cost of each node.

For the graph in previous activity, imagine node A as starting node and your goal is to reach F.
Keeping depth first search in mind, describe a sequence of actions that you must take to reach that goal
state.

Remember that we can implement depth first search simply by using LIFO approach instead of FIFO
nodes (nodes without
children) in explored set.
Now the function definition is complete which can be called as follows,

Notice the difference in two portions of the code between breadth first search and depth first search. In
the first we just pop out the last entry from the queue and in the 2 nd difference we delete leaf nodes
from the graph.

Calling DFS() will return the following solution, ['A', 'E', 'D']
Activity 2:
Change initial state to D and set goal state as C. What will be resulting path of BF S search? What
will be the sequence of nodes explored?
Solution:
Final path is ['D', 'B', 'A', 'C'] Explored node sequence is D, E, A.

3) Graded Lab Tasks

Note: The instructor can design graded lab activities according to the level of difficult and
complexity of the solved lab activities. The lab tasks assigned by the instructor should be evaluated
in the same lab

Lab Task 1:
Imagine going from Arad to Bucharest in the following map. Your goal is to minimize the distance
mentioned in the map during your travel. Implement a depth first search to find the corresponding
path.

Figure 14 - Map of Romania

Lab Task 2:
Generate a list of possible words from a character matrix
Given an M × N boggle board, find a list of all possible words that can be formed by a sequence of
adjacent characters on the board.
We are allowed to search a word in all eight possible directions, i.e., North, West, South, East, North-
East, North-West, South-East, South-West, but a word should not have multiple instances of the same
cell.
Consider the following the traditional 4 × 4
boggle board. If the input dictionary is [START,
NOTE, SAND, STONED], the valid words are
[NOTE, SAND, STONED].

Boggle Board