Algorithms - Graph Algorithms Exam Questions and Answers Fully Solved Latest Version

Algorithms - Graph Algorithms Exam Questions and Answers Fully Solved Latest Version How to get the connected components in undirected graphs? - AnswersRun DFS and keep track of component number What is the input and output of DFS when run on an undirected graph? - AnswersThe input is a graph of vertices and edges in adjacency list representation, and the output is the list of vertices labelled by connected components What does the Explore subroutine do when called by DFS? - AnswersThe DFS algorithm itself increments the connected component number. The explore subroutine sets each vertex to the current value of the connected component number and sets the visited flag to true on the vertex. It then repeats this routine on every vertex that it can reach from its current vertex. How do you find a path between connected vertices on undirected graphs? - AnswersUpdate the DFS and Explore subroutines to store a "prev" or "previous" variable for each vertex. DFS initializes the value to null for all vertices, and the explore sub routine updates this value after calling itself on each vertex that is reachable from the one it started from - sets it to the value of the input vertex How do you obtain connectivity info on directed graphs? - AnswersUpdate the DFS and Explore subroutines to use a "clock" variable that starts at 1. Each time the explore subroutine is run, it sets the pre order number to the current value of the clock and then increments the clock. When it finishes one full execution, it sets the post order number to the current value of the clock and then increments it. Why increment the clock in the Explore subroutine? - AnswersSo that no two vertices have the same pre order or post order number What are the different types of edges in a DFS graph? - AnswersTree edges, back edges, forward edges, cross edges How do the different types of edges in a DFS graph arise? - AnswersAn edge to a vertex that has already been explored. For back edges, the post order number of the ancestor is lower than that of the descendant. In all other edges, the ancestor has a higher post order number. In cross-edges, there is no apparent ancestor-descendent relation which can be observed with the pre order numbers. How can you determine a graph has a cycle using its DFS tree? - AnswersGraph G has a cycle if and only if its DFS tree has a back edge What is a DAG? - AnswersDirected Acyclic Graph (has no back edges) What is meant by a topological sorting of a DAG? - AnswersAn order of the vertices of the DAG such that all edges go from lower to higher How do you topologically sort a DAG? - AnswersRun DFS on DAG G. Since there are no back edges, all edges from z to w will have a higher post order number on z than w. After running DFS, order the vertices by decreasing post order number. What is the runtime of topologically sorting a DAG? - AnswersO(n+m) Define a source vertex in terms of edges and post order numbers - AnswersNo incoming edges and highest post-order number Define a sink vertex in terms of edges and post order numbers - AnswersNo outgoing edges and lowest post-order number Wen are two vertices v and w strongly connected? - AnswersWhen there is a path from v to w and w to v. Path implies that multiple edges can be involved.