CSE221 Lab 3 Solved

In order to do so, you have to defeat the gyms/bad guys in the places you walk into in a limited amount of time. Your goal is to get to the Victory Road as quickly as possible.

Task 1: Graph Building [5 marks]

You were given a map of the region. Create a Graph (preferably with adjacent lists) that represents all the places of the region. To help us calculate, we shall assign a number to each of the places on the map:

Sample Inputs: (You can use any of the two samples)

Create a graph using the above values!

Task 2: Breadth-First Search (BFS) [7.5 marks]

Since you are a genius and you have an idea of the BFS algorithm, you can calculate the least number of cities you need to visit to get to your destination, Victory Road. Implement a BFS algorithm to determine the places you need to visit to get to the victory road!

Sample Pseudocode for the BFS implementation: (You are allowed to try different approaches with same or less time complexity, but the outputs must match)

visited =[0]*noOfPlacesOrNodes , queue =[] BFS (visited, graph, node, endPoint)

Do visited[int(node)-1] 1 Do queue append(node) While queue not empty

#Driver

Do m pop()
Print m // [into output text file]
If m= endPoint break
For each neighbour of m in graph If visited[int(neighbour)-1] = 0

Do visited[int(neighbour)-1] 1 Do queue append(neighbour)

Read data from input.txt and create a graph BFS(visited, graph, ‘1’, ‘12’)

Sample Inputs:

Same as Task 1

Sample Output:

Places: 1 2 3 4 5 7 11 6 12

Task 3: Depth-First Search (DFS) [7.5 Marks]

Now, imagine your rival, Gary, who was also sent to the Pokémon world, wants to become Pokémon master before you. He is planning to get to Victory Road using the DFS algorithm. Implement a DFS algorithm to determine the places he needs to visit to get to the victory road!

Sample Pseudocode for the DFS implementation: (You are allowed to try different approaches with same or less time complexity, but the outputs must match)

visited =[0]*noOfPlacesOrNodes
printed = [] #this will store the graph traversing sequence DFS_VISIT (graph, node)

Do visited[int(node)-1] 1 printed.append(node)
For each node in in graph[node]

If node not visited
DFS_VISIT (graph, node)

#This part is needed if the graph is disconnected.

DFS (graph, endPoint)
For each node in in graph

If node not visited
DFS_VISIT (graph, node)

Print “printed” list in a loop till you get the end point

#Driver

Read data from input.txt and create a graph DFS(graph, ‘12’)

Sample Inputs:

Same as Task 1

Sample Output:

Places: 1 2 3 4 7 11 12

Task 4: Comparison [5 Marks]

Now, calculate the time-complexity of the BFS (Task 2) and DFS (Task 3) algorithms you used (both for matrix and adjacency list). Also show who gets to the victory road first and why.

Not mandatory task(But Try it for Yourself): (No marks)

1. Can you print the places’ names instead of the designated numbers as output?
2. The given BFS code will not work for disconnected graphs. Can you modify this

   bfs code so that it can work for disconnected graphs as well?

3. Can you detect the cycle using dfs?

   If you don’t know these, try to find it out. Take help from STs and faculties . Remember that: a bit more learning will never hurt.