学习图算法

在算法中，我主要是自学成才的，这很好。但是，我很难理解图形算法。我正在寻找一些具有概念和实际代码的参考资料，所以我不仅可以学习理论（我通常可以做到这一点），还可以了解图表在实践中如何表现和操纵图表（我通常具有更难掌握）。可以提供吗？只要有概念和实现，从书本，链接到现有项目的任何事情都会很好。学习图算法

这是语言不可知的，但我最熟悉python，并没有太多的FP经验。

来源

2010-10-27 jlv

这两者都是非常好的：

The Algorithm Design Manual
Algorithms in C++ Part 5: Graph Algorithms（别担心C++位，也有伪代码）

免费的东西：

Chapter 5. Graphs and graph algorithms

来源

2010-10-27 01:35:44

TADM刚刚提到（再次感谢，但！）但我会检查第二个肯定。 – jlv 2010-10-27 01:37:47

Steve Yegge说this是关于广泛使用图的算法的一本了不起的书。

来源

2010-10-27 01:33:09 duffymo

亚马逊愿意上市。 – jlv 2010-10-27 01:37:05

我学到了很多从下面链接的书图...这是我最喜欢的一本书： http://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover&dq=a+course+in+combinatorics&source=bl&ots=wSYYY6KPuI&sig=mZLrdj0xo2mTxW4MxYt4tW_E-10&hl=en&ei=PoHHTOaROIHGlQegn8ibAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCkQ6AEwAQ#v=onepage&q&f=false

A Course in Combinatorics 
J. H. van Lint, R. M. Wilson 
Cambridge University Press 
ISBN 0 521 00601 5

来源

2010-10-27 01:33:29

下面的网站也有一些非常酷的动画，可以帮助你理解图算法：http：//www.cs.sunysb。edu /〜skiena/combinatorica /动画/ – 2010-10-27 01:35:23

我从来没有看过combinatorics，所以我的兴趣非常高。但是，它似乎没有包含任何代码正确的？ – jlv 2010-10-27 01:38:41

jlv：没错，这本书没有代码。然而，这是一本用于学习图结构背后的数学的好书，可以应用于算法。我不会提到它，但它只是一本很棒的书。我不能*不提及它。 :) – 2010-10-28 03:15:22

我建议，当你学习任何算法则并不认为它编码的。算法是完全数学的，你必须对他们持相同的态度。当你学习像Graph Spanner算法之类的东西时，不要考虑如何编码它如何表示它们。首先明白为什么算法是重要的和不重要的。然后尝试一些非常小的解决方案并比较它们的复杂性。接下来看看最佳解决方案是怎样的，并尝试推导它们的属性。使用纸和笔而不是IDE，尝试派生并证明引号等。最后，看看如何编写伪代码来解决问题。如果你做了这些事情，那么你会发展与算法的亲密关系，然后你会发现它是更容易解决它们，因为那时你不认为在编码时，为什么我这样做。

不幸的是，由于对程序员的巨大需求，现在的程序员不是数学家，他们在解决新问题时会遇到问题。早期的程序员，如Don Knuth，Mcarthy是数学家和优秀的研究人员。因此，与计算机科学家相比，程序员现在是一个相对便宜的单词。

来源

2012-07-14 18:05:37

OTOH我个人发现实现一个算法（之前没有看到任何伪代码），并使用该实现验证了我完全理解该算法的工作原理。 – 2013-11-17 21:59:01

@MarkusUnterwaditzer - 真的，这是一个很棒的练习。请注意，尽管如此，很容易陷入糟糕的解决方案。如果你已经达到了一个看起来不合适的地步，那么看看伪代码是值得的。 – Ben 2014-02-19 20:19:47

Bellman-Ford算法：从源到即使-eve边缘权重（未循环）在加权有向图的所有其他节点最短路径。比Dijsktra慢但多才多艺。 复杂度：O（| V | | E |）

BFS：查找路径从一个给定的顶点到在未加权未向图的其他节点。 复杂度：O（| V | + | E |）。当您知道前面的顶点并使用适当的数据结构i时，速度会更快。ËFIFO阙搞清楚可以降低到ö这已经比复杂处理的顶点（| V |）

DFS：搜索由源到其他节点的最短路径。在树和图中。图表可能包含循环，这意味着节点可能会一次又一次被访问。所以我们可以使用布尔数组来跟踪访问节点。否则算法不会停止。它更多地越过越深，越远到达树的末端。 复杂度：O（| V | + | E |）。和复杂度：O（| V |）存储顶点的空间。

Floyed Warshal算法： 查找定向未加权的曲线图与+前夕，-eve（未循环）边缘权重的所有对的最短路径。但它并不返回路径的细节。它可以用来检测图中的重量周期。当它找到一个它终止。它比较每对顶点之间所有可能的路径图。所以它采用动态方法而不是贪婪的方法。 复杂度：O（| V^3 |）

约翰逊的算法：发现在向加权稀疏图所有对的最短路径时边缘权重是+前夕，-eve但不-eve周期。它首先使用贝尔福特算法从原始图形计算变换图。它消除了重量的边缘。然后应用Dijkstra来查找路径。 复杂度：O（V^2登录V + VE）

Dijkstra算法： 该算法不的原始版本使用优先阙所以复杂度为O（| V^2 |）但较新版本使用这种数据结构，因此复杂性变为O（E + V log V）。并且它是更快的单源最短路径算法。它通过给被访问节点分配一个临时权重，对被访问节点的未访问节点分配一个无穷大来查找所有未被访问的边，并以最小权重选择。并将其添加到路径集。

Krushkal's算法：找到MST，在MST中找到一个可能权重最小的边，它连接了无向图的加权图上森林中的任意两棵树。这是贪婪算法。它也发现最小生成森林。 复杂度：O（E日志V）

Prim算法：它发现形成上未定向，加权图树边缘的子集。但不能像Krushkal算法那样找到MS Forest。

Brouvka的算法：这个算法的问题是权重在图中应该是唯一的。它通过检查每个顶点然后以较小的重量来找到MST。该算法本质上是并行的，但不比Prim算法快。

与Krushkal算法一样复杂。

来源

2015-08-04 06:53:27

回答

相关问题