3. Write a version of the depth-first search algorithm, where graph G is represented by an...

 

Transcribed Image Text:

3. Write a version of the depth-first search algorithm, where graph G is represented by an adjacency matrix and the output the preorder labelling of the vertices as an integer array. You can use the code on page 367 of Goodrich and Tamassia as a starting point (given in the slides). Assume the graph is simple and connected. Do not worry about labelling the edges as explored, discovery or back edges. Focus on how you would use the adjacency matrix to find adjacent vertices and how to determine if a vertex has been explored or not yet (Hint: the preorder labels may help with that.) Algorithm matrixDFS(G,v) Input: A graph G, with n vertices labeled 0, ..., n - 1, represented as an adjacency matrix and a starting vertex v. Output: An integer array of size n, containing the preorder labelling of the vertices. 4. Analyze the best-case and worst-case running times of your matrixDFS() algorithm in question 3 above. How does this compare to the best-case and worst-case running times of implementing DFS with an adjacency list representation of the graph? 3. Write a version of the depth-first search algorithm, where graph G is represented by an adjacency matrix and the output the preorder labelling of the vertices as an integer array. You can use the code on page 367 of Goodrich and Tamassia as a starting point (given in the slides). Assume the graph is simple and connected. Do not worry about labelling the edges as explored, discovery or back edges. Focus on how you would use the adjacency matrix to find adjacent vertices and how to determine if a vertex has been explored or not yet (Hint: the preorder labels may help with that.) Algorithm matrixDFS(G,v) Input: A graph G, with n vertices labeled 0, ..., n - 1, represented as an adjacency matrix and a starting vertex v. Output: An integer array of size n, containing the preorder labelling of the vertices. 4. Analyze the best-case and worst-case running times of your matrixDFS() algorithm in question 3 above. How does this compare to the best-case and worst-case running times of implementing DFS with an adjacency list representation of the graph?

Answer rating: 100% (QA)

The depthfirst search DFS algorithm using an adjacency matrix representation of the graph to find the preorder labeling of the vertices def matrixDFSG ... View the full answer