Taking for example large (X by Y) hex map, how can I divide the map into N regions of connected hexes to simulate countries?
The goal is to generate a hex map that looks like a real life map with countries with different shapes but equal sizes.
Have you tried Lloyd's Algorithm? The procedure is pretty simple, and will generate fairly regular looking regions (depending on how many iterations you run).
You don't have to run it very long to produce a nice looking map. This example required only three iterations.
One simple way you could try.
I didn't test but this should generate Islands and somewhat avoid long thin braces. Also, Most likely there will be neighbors borders but not necessarily each one will be in touch of other, that density will depend on the value of
I definitely think some type of graph structure would make this possible. Basically create an edge between two Hex nodes if they are next to each other to simulate the whole map. However, I am not sure the exact algorithm for generating a "country" within that map. The thing is, depending on how you want the country to "look" you would need different algorithms.
Off the top of my head, I would recommend picking a point and moving outwards from there, picking a random tile within your "growing country" which has an adjacent tile that is not part of the country.
A strategy pattern could be used to switch out algorithms depending on what type of country look you want. http://en.wikipedia.org/wiki/Strategy_pattern i.e. do you want a slim coastline country like chile? Or do you want something that is more round and contained?
Graph properties may also allow you to tweak what you want the end "country" to look like: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)
Want a large country? Tweak the graph properties and force the generated country (which is just a graph) to have the properties that give it a "look" you will want.
Last but not least, Graphs will also be very useful for defining borders between countries. You could build a graph that has a connection between two nodes if countries border each other. This might be useful for some type of partitioning in your game and will allow you to possibly optimize certain things further along in development.
One small note: you say 'looks like a real life map with countries of different shapes but equal sizes), but 'real' countries are vastly different in size even within certain regions — even the 'large' countries of Europe can vary hugely, with e.g. France being more than twice as large as Italy. With that said, there are obviously gameplay regions to try and keep sizes roughly the same - just be aware that a little variation here is probably a good thing!
My initial approach to the problem would be to 'evolve' (rather than 'grow') your regions:
Now, for as long as you want, run the following pseudocode:
This will maintain a rough balance between the size of any two neighboring countries, and the 'disconnected' check (which can be done with a simple flood-fill algorithm) makes sure that no country ever breaks apart into pieces. Updating the boundary list is a constant-time operation - the changed hex will obviously always still be on the boundary, and you can just check its six neighbors to see if any of them has either become a boundary cell (because its neighbor is now in a different country) or stopped being a boundary cell (because its neighbor's in the same country now), modifying the boundary set as needed.
For a refinement of this approach, you can even make the condition of which hex to change a bit randomized - rather than always 'balancing' the two countries, you can always make the swap with a certain probability, and even gradually diminish that probability over time (similar to the cooling process in a Simulated Annealing algorithm) to start to force them to be roughly the same size.
Note that this won't guarantee that all areas are exactly the same size (which is impossible unless N perfectly divides your grid size anyway), and it won't even guarantee that all countries are within one hex of each other in area; it should guarantee (run for enough iterations) that each country is no more than one hex larger or smaller than each of its immediate neighbors, though.