What I'm looking for is a comprehensive list of graph traversal algorithms, with brief descriptions of their purpose, as a jump off point for researching them. So far I'm aware of:
What are some other well-known ones? Please provide a brief description of each algorithm to each of your answers.
Wikipedia is a good place to start with a question like this.
And if you have a spare £30, this book is awesome.
A few off of the top of my head:
Depth-first and Breadth-first traversals, really just two different ways of touching all of the nodes.
Floyd-Warshall algorithm finds the shortest paths between any pair of points, in (big-theta)(v^3) time.
Prim's algorithm is an alternative to Kruskal's for MST.
There are also algorithms for finding fully connected components, which are groups of nodes where you can get from any member in the component to any other member. This only matters for "directed graphs", where you can traverse an edge only one direction.
Personally, I think the coolest extension of graph theory (not exactly related to your question, but if you're interested in learning more about graphs in general its certainly worth your while) is the concepts of "flow networks": http://en.wikipedia.org/wiki/Flow_network . It is a way of computing about, say, how much electricity can one distribute over houses with a variety of power needs and requirements, and a variety of power stations.