GPUs have been used effectively in implementing graph algorithms. Graph algorithms are tremendously useful and show up all over computing.

http://arxiv.org/abs/1002.4482

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.220...