Chapter 3: Q10E (page 108)
Rewrite the explore procedure (Figure 3.3) so that it is non-recursive (that is, explicitly use a stack). The calls to pre visit and post visit should be positioned so that they have the same effect as in the recursive procedure.
The recursive procedure is proved.
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Run the DFS-based topological ordering algorithm on the following graph. Whenever you have a choice of vertices to explore, always pick the one that is alphabetically first.
(a) Indicate the pre and post numbers of the nodes.
(b) What are the sources and sinks of the graph?
(c) What topological ordering is found by the algorithm?
(d) How many topological orderings does this graph have?
Biconnected componentsLet G=(V,E) be an undirected graph. For any two edges, we’ll sayif eitheror there is a (simple) cycle containing both e and e'.
a. Show that : is an equivalence relation (recall Exercise 3.29) on the edges.
The equivalence classes into which this relation partitions the edges are called the biconnected components of G . A bridge is an edge which is in a biconnected component all by itself.
A separating vertexis a vertex whose removal disconnects the graph.
b. Partition the edges of the graph below into biconnected components, and identify the bridges and separating vertices.
Not only do biconnected components partition the edges of the graph, they almost partition the vertices in the following sense.
c. Associate with each biconnected component all the vertices that are endpoints of its edges. Show that the vertices corresponding to two different biconnected components are either disjoint or intersect in a single separating vertex.
d. Collapse each biconnected component into a single meta-node, and retain individual nodes for each separating vertex. (So there are edges between each component node and its separating vertices.) Show that the resulting graph is a tree.
DFS can be used to identify the biconnected components, bridges, and separating vertices of a graph in linear time.
e. Show that the root of the DFS tree is a separating vertex if and only if it has more than one child in the tree.
f. Show that a non-root vertex v of the DFS tree is a separating vertex if and only if it has a child v' none of whose descendants (including itself) has a back edge to a proper ancestor of v .
g. For each vertex u define:
Where (v,w) is a back edge for some descendant v of u.
(h) Show how to compute all separating vertices, bridges, and biconnected components of a graph in linear time.
Perform depth-first search on each of the following graphs; whenever there’s a choice of vertices, pick the one that is alphabetically first. Classify each edge as a tree edge, forward edge, back edge, or cross edge, and give the pre and post number of each vertex.
As in the previous problem, you are given a binary tree T=(V,E) with designated root node. In addition, there is an array with a value for each node in V Define a new array as follows: for each ,
the maximum of the x-values associated with u’s descendants.
Give a linear-time algorithm that calculates the entire z-array.
The chapter suggests an alternative algorithm for linearization (topological sorting), which repeatedly removes source nodes from the graph (page 101). Show that this algorithm can be implemented in linear time.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
