Very slow graph walking
Since you've only posted partial code, all we can do is offer some suggestions:


Google suggests that the performance of stdext::hash_map might be improved by adding #define _SECURE_SCL 0. See this MSDN article for background.
Your if's look like they might become victim to branch misprediction. This StackOverflow answer explains that better than I ever could.
If you haven't done so already, take care to allocate your vertices (and their internal data) contiguously. The simplest way to do that is usually to shove everything into a vector.