Connected Components Using BFS in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a connected component in an undirected graph?

A connected component is a group of nodes where each node is reachable from any other node in the same group by following edges.

beginner

How does BFS help in finding connected components?

BFS explores all nodes reachable from a starting node. By running BFS from unvisited nodes, we find all nodes in that connected component.

beginner

What data structure is commonly used to implement BFS?

A queue is used to keep track of nodes to visit next in BFS.

beginner

In BFS for connected components, why do we mark nodes as visited?

Marking nodes as visited prevents revisiting the same node, avoiding infinite loops and repeated work.

intermediate

What is the time complexity of finding connected components using BFS in a graph with V vertices and E edges?

The time complexity is O(V + E) because each vertex and edge is visited at most once during BFS.

What is the first step when using BFS to find connected components?

A Mark all nodes as visited

B Start BFS from an unvisited node

C Add all nodes to the queue

D Remove edges from the graph

We start BFS from an unvisited node to explore its connected component.

Which data structure is essential for BFS traversal?

A Heap

B Stack

C Queue

D Set

A queue is used to process nodes in the order they are discovered in BFS.

How do you know when you have found all connected components in a graph?

A When BFS runs once

B When the queue is empty

C When all edges are removed

D When all nodes are visited

All connected components are found when every node in the graph has been visited.

What happens if you do not mark nodes as visited in BFS?

A You may visit nodes multiple times causing infinite loops

B BFS will run faster

C The graph will change

D Edges will be ignored

Without marking visited nodes, BFS can revisit nodes repeatedly, causing infinite loops.

What is the main goal of BFS in connected components?

A To explore all nodes in one connected component

B To sort nodes by value

C To find the shortest path between two nodes

D To remove cycles

BFS explores all nodes reachable from a starting node, identifying one connected component.

Explain step-by-step how BFS is used to find all connected components in an undirected graph.

Think about visiting nodes and marking them to avoid repeats.

Describe why marking nodes as visited is important in BFS when finding connected components.

Consider what happens if you visit the same node multiple times.