Working on compilers, graph algorithms of various kinds tend to come up rather frequently. The only one that I recall having to implement myself was enumerating elementary cycles in a graph. That said, you often have to do a modified standard tree or graph traversal, so some variant of BFS or DFS is pretty common.
The only other exotic data structure I've had to use is the union-find data structure. It's a pretty slick data structure, both because it's so easy that you could probably come up with the optimal one just by thinking about it for a few hours, but also because its runtime is O(n * inverse Ackermann(n)), the latter function grows so slowly that it is less than 4 for the number of atoms in the universe. Although, unfortunately, the data structure doesn't do a good job of telling you which union call is the one that merged two sets that should be separate together.
The only other exotic data structure I've had to use is the union-find data structure. It's a pretty slick data structure, both because it's so easy that you could probably come up with the optimal one just by thinking about it for a few hours, but also because its runtime is O(n * inverse Ackermann(n)), the latter function grows so slowly that it is less than 4 for the number of atoms in the universe. Although, unfortunately, the data structure doesn't do a good job of telling you which union call is the one that merged two sets that should be separate together.