Difference between pages "3.21" and "8.25"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(Created page with "Since all the elements in S2 have keys larger than the keys of the elements in S1, those two trees can be subtrees of one tree whose root node will have a key larger than the...")
 
(Created page with "Step 1: Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m) Step 2: Go through vertices in topological order. Initially all vertic...")
 
Line 1: Line 1:
Since all the elements in S2 have keys larger than the keys of the elements in S1, those two trees can be subtrees of one tree whose root node will have a key larger than the largest key in S1 and smaller than the smallest key in S2. Then S2 will be the right subtree and S1 the left subtree. The easiest way to do this is to find the minimum element of S2 (or the maximum of S1) and put it as the root of the concatenated tree and than update its left and right pointer to point to the root of S1 and S2 respectively. The worst-case running time will be O(h), which is the time of retrieving the minimum (maximum) element of a tree.
+
Step 1:
  
 +
Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m)
  
Back to [[Chapter 3]]
+
Step 2:
 +
 
 +
Go through vertices in topological order. Initially all vertices marked as inaccessible and only starting vertex marked with 0 distance.
 +
For every vertex in cycle, if it is accessible, we update all its children with new distance if new distance is shorter then previous one.
 +
Topological sorting ensures that we don't ever need to go backtrack. This is O(n + m).
 +
 
 +
Total running bound is O(n+m), which is linear as requested.
 +
 
 +
 
 +
Back to [[Chapter 8]]

Latest revision as of 14:11, 21 September 2020

Step 1:

Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m)

Step 2:

Go through vertices in topological order. Initially all vertices marked as inaccessible and only starting vertex marked with 0 distance. For every vertex in cycle, if it is accessible, we update all its children with new distance if new distance is shorter then previous one. Topological sorting ensures that we don't ever need to go backtrack. This is O(n + m).

Total running bound is O(n+m), which is linear as requested.


Back to Chapter 8