New Month End Dhamaka - Flat 55% Off on All Courses

    Question

    Which traversal method is most suitable for finding

    connected components in an undirected graph?
    A Breadth-First Search (BFS) Correct Answer Incorrect Answer
    B Depth-First Search (DFS) Correct Answer Incorrect Answer
    C Topological Sort Correct Answer Incorrect Answer
    D Dijkstra’s Algorithm Correct Answer Incorrect Answer
    E Floyd-Warshall Algorithm Correct Answer Incorrect Answer

    Solution

    Depth-First Search (DFS) is ideal for finding connected components in an undirected graph. Starting from an unvisited vertex, DFS explores all reachable vertices, marking them as visited. Each DFS call identifies one connected component, and the process is repeated for all unvisited vertices. Steps: 1. Initialize all vertices as unvisited. 2. Perform DFS from each unvisited vertex. 3. Each DFS traversal marks a connected component. DFS is efficient, with a time complexity of O(V+E), making it well-suited for sparse and dense graphs. Why Other Options Are Incorrect: 1. BFS: Can also find connected components but requires more memory due to queue-based implementation. 2. Topological Sort: Applies to Directed Acyclic Graphs (DAGs) and does not determine connected components. 3. Dijkstra’s Algorithm: Finds shortest paths, not connected components. 4. Floyd-Warshall Algorithm: Computes all-pairs shortest paths, unsuitable for this task.

    Practice Next