Question

Exercise 2: BFS, DFS, UCS

Question #1.

Figure 1

Consider the search problem represented in Figure 1, where s is the start node, give the visited node order for Breadth First Search and Depth First Search.

2. Question #2

Figure 2

• Give a possible order in which the nodes of this figure 2 could be visited in performing a Breadth First Search (BFS) starting at C. nodes are visited in alphabetical order (when multiple choices are possible).

• Give a possible order in which the nodes of this figure 2 could be visited in performing a Depth First Search (DFS) starting at C. nodes are visited in alphabetical order (when multiple choices are possible).

• Give a possible order in which the nodes of this figure 2 could be visited in performing a Cost Search (UCS) starting at C. nodes are visited in alphabetical order (when multiple choices are possible).

Introduction to Artificial intelligence

Answer 1

1. All graph problems are solved by search method such that the commonly used search methods are

• Breadth First Search
• Depth First Search

Given below figure 1 is a connected graph with 's' is the start node

Breadth First Search

In this search algorithm,first we have to visit start vertex 's' (fig 1) and put it into the queue by using FIFO. Then repeatedly remove that vertex from the queue and visit its adjacent vertices and again put newly visited vertices in to the queue

Therefore our visited node order = s,t,u,w,x,v,y,z

Depth First Search

• First start at the vertex 's' and do dfs in either t and u.
• If the vertex 2 is selected label vetrex t and do dfs either v and w as follows.
• visited node order= s,t,v,y,z,u,w,x

2. Given below Figure 2 shows a tree with nodes and performing visited nodes in BFS, DFS and UCS

Figure 2. Tree

• Breadth First search visited node order= C,D,E,F,G,H,I
• Depth First Search visited node order= C,E,I,H,D,G,F
• Uniform Cost Search: In this algorithm we visit the start node at first and will visit the adjacent nodes will choose the least costly nodefrom the un-visited nodes.

The visited node comes like this: C,D,F,G,E,I,H