Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 13
Exercise 1 (hand-in):
Take a look at the digraph from exercise 11.13 in the main textbook.
- Draw the resulting BFS spanning tree and one of the possible
sequences of nodes visited during BFS of the digraph.
There are many correct answers.
- Draw the resulting DFS spanning tree and one of the possible
sequences of nodes visited during DFS of the digraph.
There are many correct answers.
Exercise 2:
- Write an algorithm reachable_nodes(g:DIGRAPH, v:VERTEX_TYPE):int
which returns the number of nodes reachable from a given node v.
The node v should be included in the counting.
(Hint: Use BFS as a procedure in your program.)
- Let us consider that every node has a distance field.
Modify the BFS algorithm such that after the execution of
bfs(g,a) for every vertex v the field
v.distance contains the length of the shortest path from
the start vertex a to v.
Exercise 3:
Model the organization scheme of your semester project as a DAG
with cost (include only the main tasks - cca 10 to 20 nodes).
Try to put as many steps in parallel as possible and estimate
the time each task takes by a unit price (1 unit = 1 week of work).
- What is the critical path for your group in this semester?
- What is the minimal time required to
complete all the tasks provided that
an optimal work distribution among the group members is possible?
Exercise 4:
Rewrite the algorithm dfs(g:DIGRAPH,a:VERTEX_TYPE) such that
instead of recursion it uses a stack to remember which nodes
have to be yet investigated.