Course contentsShow
← Computer Science
Lesson 733 of 2,87217. Graph Traversal AlgorithmsFree lesson

Component Labeling Algorithm

Assign unique labels to vertices during traversal to identify which component each vertex belongs to.

Component Labeling Algorithm

What you'll learn: How to assign unique labels to vertices during graph traversal so you can identify which connected component each vertex belongs to.

The Core Idea

Imagine you're organizing students into project groups in a classroom. You give each group a different colored sticker—Group 1 gets red, Group 2 gets blue, and so on. The component labeling algorithm does exactly this for graphs: it visits each vertex and assigns it a group number (label) that identifies its connected component.

You've already learned how to count components and find them using DFS or BFS. Now you're taking it one step further: you're creating a mapping that tells you "vertex A is in component 0, vertex B is in component 1," and so on.

How It Works

Start with an array or map to store labels for each vertex. Initialize all labels as unassigned (e.g., -1). Then:

  1. Iterate through all vertices in the graph
  2. When you find an unlabeled vertex, start a DFS or BFS from it
  3. During the traversal, assign the current component number to every reachable vertex
  4. Increment the component counter and repeat for the next unlabeled vertex

The result is a data structure where label[v] tells you which component vertex v belongs to. Vertices with the same label are in the same component; vertices with different labels are in different components.

Why This Matters

Component labeling lets you quickly answer questions like "Are vertices X and Y in the same component?" by simply checking label[X] == label[Y] in constant time. This is extremely useful in network analysis, image processing, and clustering problems.

Key Takeaway: Component labeling extends component detection by assigning each vertex a unique group identifier during traversal, enabling fast connectivity queries.