在算法方面，我大多数时间都是自学的，这通常没有问题。然而，我现在有点难以理解图形算法。我正在寻找一些参考资料，其中包括概念和实际代码，这样我不仅可以学习理论（通常我做得还可以），还可以了解如何在实践中表示和操作图形（我通常更难掌握）。能否提供一些相关的书籍、链接或现有项目等内容呢？只要它们具备概念和实现两个方面，就可以。
这是与编程语言无关的，但我最熟悉Python，并且没有太多函数式编程经验。
5个回答
2
我从下面链接的书籍中学到了很多关于图形的知识... 这是我最喜欢的书之一：
组合数学导论
J. H. van Lint, R. M. Wilson
出版社：剑桥大学出版社
ISBN 0 521 00601 5
- Madison Caldwell
1
1以下网站还有一些非常酷的动画，可以帮助您理解图形算法：http://www.cs.sunysb.edu/~skiena/combinatorica/animations/。 - Madison Caldwell
1
我建议你在学习任何算法时，不要考虑编码。算法完全是数学的，你必须对它们有相同的态度。当你学习像图形跨度算法这样的东西时，不要想着如何编码或者如何表示它们。首先要欣赏算法为什么重要和非平凡。然后尝试一些非常琐碎的解决方案并比较它们的复杂性。接下来看看最优解长什么样子，并尝试推导它们的属性。使用纸和笔而不是IDE，尝试推导和证明引理等。最后看看如何编写伪代码来解决问题。如果你做这些事情，你将会与算法建立亲密的关系，然后你会发现解决它们变得更容易，因为你不会在编码时思考为什么要这样做。
不幸的是，由于对程序员的巨大需求，现在的程序员不是数学家，他们在解决新问题时面临困难。早期的程序员，如Don Knuth、Mcarthy都是数学家和优秀的研究人员。因此，与计算机科学家相比，现在的程序员是一个相对便宜的词。
不幸的是，由于对程序员的巨大需求，现在的程序员不是数学家，他们在解决新问题时面临困难。早期的程序员，如Don Knuth、Mcarthy都是数学家和优秀的研究人员。因此，与计算机科学家相比，现在的程序员是一个相对便宜的词。
- Dipendra Kumar Mishra
0
贝尔曼-福特算法：在加权有向图中，从源节点到所有其他节点的最短路径，即使存在负边权（非循环）。比迪杰斯特拉算法慢但更灵活。 复杂度：O(|V|.|E|)
BFS：在无权无向图中找到从给定顶点到其他节点的路径。 复杂度：O(|V|+|E|)。当您提前知道顶点并使用适当的数据结构，例如FIFO队列来确定哪个顶点已经处理过时，它会更快，并且可以将复杂度降低到O(|V|)
DFS：在树和图中找到从源节点到其他节点的最短路径。图可能包含循环，这意味着一个节点可能被反复访问。因此，我们可以使用布尔数组来跟踪已访问的节点，否则算法将不会停止。 此外，它会更深入地查找并沿树的分支一直走到末端。 复杂度：O(|V|+|E|)。以及用于存储顶点的复杂度：O(|V|)的空间。
Floyed Warshal Algorithm: Floyed Warshal算法：在有向无权图中查找所有对最短路径，包括+eve、-eve（非循环）边权重。但它不返回路径本身的详细信息。它可以用于检测图中的-eve权重循环。当它发现一个时，它就会终止。它比较每对顶点之间通过图的所有可能路径。因此，它使用动态方法而不是贪婪方法。 复杂度：O（|V^3|）
Johnson's Algorithm: Johnson算法：在有向稀疏加权图中查找所有对最短路径，当边权重为+eve、-eve但不是-eve循环时。它首先使用Belman-Ford算法从原始图计算变换后的图。它删除-eve权重边。然后应用Dijkstra查找路径。 复杂度：O（V^2 Log V + VE）
Dijkstra Algorithm: Dijkstra算法：这个算法的原始版本不使用优先队列，所以复杂度为O（|V^2|），但新版本使用这种数据结构，所以复杂度变为O（E+ V log V）。它是更快的单源最短路径算法。它通过为访问过的节点分配一个暂定权重和无限制的未访问节点来工作，对于已访问的节点，查找其所有未访问的边并选择最小权重。然后将其添加到路径集中。
Krushkal's Algorithm: 用于在无向加权图的森林中找到连接任意两个树的最小可能权重边的MST。这是一种贪心算法。它还可以找到最小生成森林。复杂度：O（E log V）
Prim's Algorithm: 它在无向加权图上找到形成树的边的子集，但不能像Krushkal's Algorithm那样找到MS Forest。
Brouvka's Algorithm: 这个算法的问题在于图中的权重应该是唯一的。它通过检查每个顶点然后与较小的权重放置来找到MST。这个算法是并行的，但不比Prim's Algorithm更快。与Krushkal's Algorithm的复杂度相同。
- Kaleem Ullah
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接