Connected Components Using BFS in DSA Typescript - 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 through edges.

beginner

How does BFS help in finding connected components?

BFS explores all nodes reachable from a starting node, marking them as visited. This helps identify one connected component at a time.

beginner

What data structure is commonly used to implement BFS?

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

intermediate

In BFS for connected components, what do you do when you find an unvisited node?

Start a BFS from that node to find and mark all nodes in its connected component.

intermediate

Why do we need to check all nodes in the graph when finding connected components?

Because the graph may have multiple disconnected parts, and BFS from one node only finds one connected component.

What does BFS use to keep track of nodes to visit next?

A Queue

B Stack

C Set

D Array

BFS uses a queue to explore nodes level by level.

What is the main goal of BFS when finding connected components?

A To visit all nodes in one connected component

B To find cycles

C To sort nodes

D To find shortest path between two nodes

BFS visits all nodes reachable from a start node, identifying one connected component.

If a graph has 3 connected components, how many BFS runs are needed to find them all?

A 1

B 2

C 3

D Depends on graph size

Each BFS run finds one connected component, so 3 runs for 3 components.

What do you do when BFS finishes exploring one connected component?

A Stop the algorithm

B Start BFS from another unvisited node

C Remove edges

D Sort the nodes

To find all components, start BFS from unvisited nodes after each BFS finishes.

Which graph type is suitable for connected components using BFS?

A Directed graph only

B Both directed and undirected graphs

C Weighted graph only

D Undirected graph only

Connected components are usually defined for undirected graphs.

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

Think about visiting nodes layer by layer and marking them.

Describe why BFS alone from one node does not find all connected components in a graph.

Consider what happens if the graph has isolated groups.