This is why I created all the dungeons in Red Rogue as images. Flash's BitmapData.fill runs at native speed, so it's faster than any algorithm you could possibly write in actionscript. Testing room connection was simply a matter of seeing if it had ended up a new colour.
http://www.robotacid.com/flash/red_rogue/mapping_demo/I tried making a graph to help with the issue of gravity.
http://www.robotacid.com/flash/red_rogue/connections/But what I didn't realise was that when the ladders are pushed out they can end up dropping into a new room - missing a drop and making an impossible to escape pit.
Solution? Double the size of the image and draw pixels on top of every surface and up every ladder. Then floodfill. BitmapData.getColorBoundsRect instantly reveals any detached surface.
Floodfill even let me do gate and key puzzles really quickly.
I'm really not looking forward to writing one when I start using a proper language.