标签归档:

图—最短路径 Dijkstra, SPFA, Floyd

最短路径一看到最,职业病一般的就会想到用动态规划来做。。。至少事实证明的确存在动态规划的解法,但就像上一篇文章中分析的那样,这是一个具有最优子结构的问题,所以我们可以用优雅的贪心算法来解决。

这里我们用来做测试的图如下图所示,还是相当给力了

最短路径

最短路径要解决的实际问题,其实通过名字[……]阅读全文

图—最小生成树 Prime 和 Kruskal 算法

图的最小生成树的算法,这个问题要解决的问题场景很简单,要给几个地方修建铁路把它们连接起来。

如下图,黑色加粗的边表示是最小生成树的边。
最小生成树

如果最理想的情况,可以假设我们知道任意一点到其他点的距离,也就是边的权重,整个图应该是连通的,那我们开始修路吧
其实这里有一个变形,我们在教科书中[……]阅读全文

数据结构复习—图

图我觉的是数据结构中的最高境界了,其实想想,链表是图,所以栈,队列,字符串 都可以理解为图;树是图,所以各种树,森林,堆等数据结构都可以理解为图。。。。生活中的各种物品,事情,关系,工程项目中的工作,计划,代码 非常非常多的东西都能理解为图,所以可以看到图这种数据结构是多么的普遍而具有通用性。[……]阅读全文