Where to get graphs to test my search algorithms against?
Search the inter-webs. 

SNAP is a set of networks hosted by a prof at Stanford. Several real world examples in a variety of settings.

Net Wiki is hosted by a UNC math prof., again several links to real datasets as well as links to other data resources.

OpenFlights Has airports and routes between them (spatial network).

OpenStreetMap user edited network of roads for most of the world. You can also download subsets (e.g. just roads in Ohio, or just highways in North America). Format is in xml, not super easy to parse, but its a real world ~2d cyclic network.

There are several other resources as well, you'll just have to dig a little.