MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -Which of the algorithms given below can be used to most efficiently determine the presence of a cycle in a given graph? Explanation: Using dfs algorithm or bfs algorithm, time complexity: O(V+E) and space complexity: O(V) are the most efficient algorithm among the given options.

Detailed explanation-2: -To detect a cycle in a directed graph, we can either use the Depth First Search or the Breadth First Search approach. In the DFS technique, we check if there exists a back edge in the DFS tree of the graph because the existence of the back edge indicates the presence of a cycle.

Detailed explanation-3: -Approach: Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then return true else return false.

Detailed explanation-4: -We can use a traversal algorithm, either depth-first or breadth-first, to find the connected components of an undirected graph. If we do a traversal starting from a vertex v, then we will visit all the vertices that can be reached from v. These are the vertices in the connected component that contains v.

Detailed explanation-5: -Explanation: The Boruvka’s algorithm, Prim’s algorithm and Kruskal’s algorithm are the algorithms that can be used to find the minimum spanning tree of the given graph.