QuickGraph
QuickGraph is a graph library for .NET that is inspired by Boost Graph Library.
QuickGraph provides generic directed/undirected graph datastructures and algorithms for .Net 2.0 and up. QuickGraph comes with algorithms such as depth first seach, breath first search, A* search, shortest path, k-shortest path, maximum flow, minimum spanning tree, least common ancestors, etc… QuickGraph supports MSAGL, GLEE, and Graphviz to render the graphs, serialization to GraphML, etc…
There are several ways to build graphs. The C++ Boost Graph Library (BGL) would be your best reference. It implements both adjacency-list, adjacency-matrix and edge-list graphs.
Look here for details.