QuikGraph库介绍
项目地址：https://github.com/KeRNeLith/QuikGraph
QuikGraph为.NET提供了通用的有向/无向图数据结构和算法。
QuikGraph提供了深度优先搜索、广度优先搜索、A*搜索、最短路径、k最短路径，最大流量、最小生成树等算法。
QuikGraph最初由Jonathan “Peli” de Halleux于2003年创建，并命名为QuickGraph。随后更新为YC.QuickGraph。
这个版本的QuickGraph，改名为QuikGraph，是YC.QuickGraph的一个分支。我尝试使用现代C#开发（.NET Core）清理该库，将其作为一个干净的NuGet包提供。该计划旨在全面清理、修复原始库及其所有非核心部件的问题，并对其进行改进。
示例
- 创建一个.Net Framework4.7.2框架的项目。
- 在NuGet上搜索QuikGraph，并安装。
- 引入命名空间：
using QuikGraph.Algorithms.Observers;
using QuikGraph.Algorithms.ShortestPath;
using QuikGraph;
- 主要测试代码：
public void DijkstraSimpleGraph()
{
// 创建邻接图，使用string类型作为顶点、边的唯一标识
var graph = new AdjacencyGraph<string, Edge<string>>(true);
// 添加顶点到图中
graph.AddVertex("A");
graph.AddVertex("B");
graph.AddVertex("D");
graph.AddVertex("C");
graph.AddVertex("E");
// 创建边
var a_b = new Edge<string>("A", "B");
var a_c = new Edge<string>("A", "C");
var b_c = new Edge<string>("B", "C");
var b_e = new Edge<string>("B", "E");
var c_d = new Edge<string>("C", "D");
var d_e = new Edge<string>("D", "E");
var e_d = new Edge<string>("E", "D");
// 添加边到图中
graph.AddEdge(a_b);
graph.AddEdge(a_c);
graph.AddEdge(b_c);
graph.AddEdge(c_d);
graph.AddEdge(d_e);
graph.AddEdge(b_e);
graph.AddEdge(e_d);
// 定义边的权重
var weight = new Dictionary<Edge<string>, double>(graph.EdgeCount)
{
[a_b] = 30,
[a_c] = 15,
[b_c] = 10,
[b_e] = 20,
[c_d] = 40,
[d_e] = 4,
[e_d] = 2,
};
// 创建算法，传入图和权重
var algorithm = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, e => weight[e]);
// Attach a Vertex Predecessor Recorder Observer to give us the paths
// 使用顶点前置记录器，以提供路径计算
var predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
using (predecessorObserver.Attach(algorithm))
//以顶点A为起点，运行算法
algorithm.Compute("A");
//打印A为起点，到各个点的距离
foreach (var vertex in graph.Vertices)
{
Trace.WriteLine($"A-{vertex} = {algorithm.GetDistance(vertex)}");
}
}
打印输出结果（打印了A为起点，到各个顶点的距离）：
A-A = 0
A-B = 30
A-D = 52
A-C = 15
A-E = 50
图结构示意（可以人工检查输出结构的正确性）：
