QuickGraph provides generic directed/undirected graph datastructures and algorithms for .NET. QuickGraph comes with algorithms such as depth first seach, breath first search, A* search, shortest path, k-shortest path, maximum flow, etc...
See the version list below for details.
New graph algorithms for graph partition, coloring, searching paths, etc
Graphs now can be loaded from DOT
Drop Portable Class Library support