Interesting - I wrote pretty much exactly the same code for chapter 2 of Hello Python, except I build a tree first (by adding each cave in sequence at a random point) and then add some random two-way connections, rather than trying to find islands later.

http://manning.com/briggs/ if you're interested in checking it out. I follow a similar route - teach programming by jumping in on something cool (eg. a game) and explain things as you go.