【QuikGraph】C#调用第三方库计算有向图、无向图的连通分量

本文主要是介绍【QuikGraph】C#调用第三方库计算有向图、无向图的连通分量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

QuikGraph库

项目地址：https://github.com/KeRNeLith/QuikGraph

相关概念

图论、连通分量、强连通分量相关概念，可以从其他博客中复习：
https://blog.csdn.net/weixin_50564032/article/details/123289611
https://zhuanlan.zhihu.com/p/37792015

有向图计算连通分量示例

测试环境参考：https://blog.csdn.net/liqian_ken/article/details/138544718

主要测试代码：

      // 创建有向邻接图，使用string类型作为顶点、边的唯一标识var graph = new AdjacencyGraph<string, Edge<string>>(true);// 添加顶点到图中graph.AddVertex("A");graph.AddVertex("B");graph.AddVertex("D");graph.AddVertex("C");graph.AddVertex("E");graph.AddVertex("F");graph.AddVertex("G");graph.AddVertex("H");// 创建边var a_b = new Edge<string>("A", "B");var a_c = new Edge<string>("A", "C");var d_e = new Edge<string>("D", "E");var e_f = new Edge<string>("E", "F");var g_h = new Edge<string>("G", "H");// 添加边到图中graph.AddEdge(a_b);graph.AddEdge(a_c);graph.AddEdge(d_e);graph.AddEdge(e_f);graph.AddEdge(g_h);var components = new Dictionary<string, int>();var cnt = graph.WeaklyConnectedComponents(components);Trace.WriteLine($"共有{cnt}个连通分量。");foreach (var pair in components.GroupBy(x => x.Value)){var str = string.Join(" ", pair.ToArray().Select(x => x.Key));Trace.WriteLine($"第{pair.Key + 1}个连通分量包含结点：{str}");}

打印输出结果：

共有3个连通分量。
第1个连通分量包含结点：A B C
第2个连通分量包含结点：D E F
第3个连通分量包含结点：G H

图结构示意：

无向图计算连通分量示例

在上述代码基础上替换一个类UndirectedGraph和一个方法ConnectedComponents：

var graph = new UndirectedGraph<string, Edge<string>>(true);...var cnt = graph.ConnectedComponents(components);

这篇关于【QuikGraph】C#调用第三方库计算有向图、无向图的连通分量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---