Homework 10
METU CENG310
Data Structures and Algorithms with Python
1 DFS and BFS
For the directed graph given below, list the node labels in (a) breadth-first search (BFS) and (b) depth-first
search (DFS) order starting from node a. There may be more than one solution to this problem, so do not try
to enumerate every single one of them. One solution for each of the DFS and BFS ordering is sufficient.
2 Weighted Shortest Path
Given the graph below, fill in the table below with the execution steps of Dijkstra’s weighted shortest path
algorithm starting from node S.
Step # visited nodes (*) dist values for nodes in U (**)
1 - (0,S)
2 (S,0) (4,G), (11,H), (33,P)
3 (S,0), (G,4) (10,R), (11,H), (11,P)
4
5
...
...
Table 1: (*) visited nodes and their shortest distances from start, (**) dist values for nodes in U (only finite
values, listed in increasing order).
1
3 Instructions
Pertaining to the answers of this homework, correct typing of superscripts (e.g., n
2
) and subscripts (e.g., n0)
matters. Due to this reason, this homework may be done on paper and returned as a PDF file containing
the answer sheet captures (photos, scanned files). If you would like you can use MS Word or Latex, but your
deliverable has to be a single PDF file. PDF file should be created so that the answers appears in the same
order as the questions shown in the homework assignment document.
A Homework-10 page will be generated soon after the start date of this homework. All deliveries should
be done over ODTUClass. Please also be aware of the late penalties (Please check the Announcements –
Homework and Assignment Policy in ODTUClass if you have not already done so.). Should you have any
questions pertaining to homework tasks, please ask them in advance (not on the due date) for your own
convenience.
2
