Is there an algorithm to determine contiguous colored regions in a grid?

Question

Given a basic grid (like a piece of graph paper), where each cell has been randomly filled in with one of n colors, is there a tried and true algorithm out there that can tell me what contiguous regions (groups of cells of the same color that are joined at the side) there are? Let's say n is something reasonable, like 5.

I have some ideas, but they all feel horribly inefficient.

Answer 1

The best possible algorithm is O(number of cells), and is not related to the number of colors.

This can be achieved by iterating through the cells, and every time you visit one that has not been marked as visited, do a graph traversal to find all the contiguous cells in that region, and then continue iterating.

Edit:

Here's a simple pseudo code example of a depth first search, which is an easy to implement graph traversal:

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}