4. This is adapted from Spring 2011 Exam 2 Question 3. Consider the following di

Question

4. This is adapted from Spring 2011 Exam 2 Question 3. Consider the following directed acyclic graph. The given graph represents a project with various tasks depicted by the circles (nodes). The time it takes to complete each task is shown beside each node below. A task cannot start unless all its predecessors have been completed. The project starts with task G and ends with task J O(G 3 E 0:4 4(C 5 B P)4 4 Write down the ordering of nodes produced when you run the depth-first-search-based topo- logical sort algorithm on the graph. Assume that the vertices are sorted in alphabetical order in the array representing the nodes and also in the linked lists representing the edges. Also indicate beside each node the start and end time stamps (d[] and f-] in the pseudo-code given in the lecture notes) when the node was traversed (or was on the code stack) Determine the earliest finish time of the entire project and the slack of each task Earliest finish time: Slack

Explanation / Answer

In the given problem, we have been asked to apply DFS bases topological sort on the given graph starting from the vertex G.

Let us understand how topological sort is done using DFS.

Whenever the DFS come across any unvisited node in the graph, it assign it a start time and perform.

After visiting all the child nodes of the nide, DFS assign it a finish time.

Each time DFS visits any node, value of time is incremented and assigned to that node and node is marked as visited.

It is given that verteces are stored in alphabatical order, this means while visiting the children of a node, DFS will follow alphabetical order.

After applying DFS, the nodes are sorted in the order of their finish time, this sorting gives us topologically sorted vertices

When applying DFS, the start and finish time of the vertices are:

Order of nodes produced in topological sort:

Slack can be calculated by subtracting starting time from finish time:

Node A B C D E F G H I J K L M N O P Start 1 3 2 4 23 11 0 10 13 5 24 14 25 16 29 15 Finish 22 8 9 7 28 12 31 21 20 6 27 19 26 17 30 18

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.