GraphAlgorithms:用 Java 编写的图形数据结构和算法库

图数据结构和算法 未加权、无向图（隐式边） 深度优先搜索 计算从源 s 到目标 t 的可达性。 计算图的连通性（连接的组件）。 图遍历/探索 也可用于查找 2 个节点之间的最短路径。 对于真正的大图（如兴趣）不利，因为它只会继续向下（如点击维基百科文章）（ ） 广度优先搜索，运行时间 O(|V|+|E|) 可以计算无权无向图的最短路径 测试二分性 如果您知道目标节点在“附近”，则很好 与深度优先搜索一样，BFS 遍历给定图的连通分量并定义生成树。 连接的组件 未加权的有向图（隐式边） 深度优先搜索 广度优先搜索 强连接组件 拓扑排序 循环检测 加权无向图（显式边） 最小生成树 普里姆 克鲁斯卡尔 加权有向图（显式边） 最短路径 Dijkstra（无负权重） Bellman-Ford（处理负权重） 笔记： 通常，adj 列表比 adj 矩阵使用的更多。 然而： 对