For a 2D grid, like in the image you posted.
While probably not the most efficient in terms of speed and memory usage, I find that a brute force approach could still be useful, since it's easy to get it started. Especially if this is not to be used in places with time or memory constraints.
//Get some random cells for countries to start extending from.
for each Country in Countries
Cell unoccupiedCell = Map.GetRandomUnoccupiedCell()
Country.OccupiedCells.Add(unoccupiedCell)
unoccupiedCell.occupier = Country
end for each
//Extend each country at random
while Map.UnoccupiedCells.Count > 0
for each Country in Countries
Cell unoccupiedCell = Map.RandomUnoccupiedCellInVicinityOf(Country)
if (unoccupiedCell exists)
Country.OccupiedCells.Add(unoccupiedCell)
unoccupiedCell.Occupier = Country
endif
end for each
end while