as Morgan Allen commented, the MST does ensure all rooms will be connected. Other connections will also be formed to add variation.
The layout looks great, but the point I wanted to make about the graph structure wasn't just making the rooms accessible, but ensuring actual cycles in the room network. The reason for this is that cycles allow for choices in how to approach specific targets or problems.
If I might take the liberty of illustrating the point with an example dungeon populated with various frivolous yet terrifying dangers-http://s22.postimg.org/d1k65n3a9/dungeon_layout.gif
Let us suppose that our Noble and Photogenic Hero wishes to secure a lifetime's supply of chocolate. S/he now has at least three options for tackling the problem- go through the Lohan-Montana hybrid followed by the Grue, go through Rube Goldberg and then the Dragonz, or discover the secret passage that allows the latter to be bypassed. The Grue can be kept at bay simply by lighting a torch, but those are in limited supply, and might be used up searching for traps (such as those laid by Mr. Goldberg) or secret passages (which also reveal the S.V. Love-Shrine, which confers immunity to the Lohan-Montana Hybrid.) So there are quite a few tradeoffs and decisions to be made within that pretty simple framework, which might be further complicated by how much the player knows or can find out about impending obstacles. And of course, terrain along the way could be used as an asset to the player (e.g, flooded passages being impassable to Dragonz.)
Anyway, sorry to derail. Like I said, the layout looks very varied and the algorithm is fascinating. But my point is that if there were only one
way to reach the lifetime's supply of chocolate, then regardless of the obstacles presented, there are far fewer tradeoffs to be considered, because the player has no choice in the matter.