Data Structures and Algorithms 3. DFS and BFS of a Graph. [10 marks total; 5 mar
ID: 3694321 • Letter: D
Question
Data Structures and Algorithms
3. DFS and BFS of a Graph. [10 marks total; 5 marks each (a) Show the operation of depth-first search (DFS) on the graph of Figure 1 starting from vertex q Always process vertices in alphabetical order. Show the discovery and finish times for each vertex and the classification of each edge. (b) A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first search (BFS) tree can also be used to classify the edges reachable from the source of the search into the same four categories. Prove that in a BFS of an undirected graph, the following properties hold: There are no back edges and no forward edges. » For each tree edge (u, v), we have v.d- u.d + 1. Here d is the distance attribute of a vertex u; it is the distance from the source to the vertex u computed by the BFS. . For each cross edge (u, u), we have u.d u.d or u.-u.d + 1.Explanation / Answer
a) In the given graph starting from the vertex q we can hae a depth first traversal in the order of
q-r-s-t-u-v-w-x-y-z
In this move from q-r the edge will be cross edge.
In r-s the edge will be back edge
In s-t it will be cross edge
In t-u again it will be cross edge
from u-v it will be back edge
from v-w it is tree edge
from w-x and x-y it is cross edges
finally from y-z it is back edge
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.