DepthFirstSearch (DFS) : parent node; discovery/finishing time; parenthesis theo

Question

DepthFirstSearch (DFS) : parent node; discovery/finishing time; parenthesis theorem.

Requirements: implement/update specific methods for the DFS of a graph; for at least 2 graphs (1 being the provided one), show the DFS order of vertices in the graph, and for each node, specify its parent node in the search (the node from which the currect node was reached). Moreover, display for each node the discovery and finishing time, to check that the Parenthesis Theorem holds true.

Approach:You may start from the DFT in the textbook and do the appropriate changes. For counting the dfs time, you should set a global counter (let

Explanation / Answer

for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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