0%

写在前面


我不信南瓜会这么整齐得在地里没人收。

阅读全文 »

写在前面

莫里斯遍历(Morris Traversal)是一种时间复杂度为O(n),空间复杂度为O(1),且不改变树的结构的二叉树遍历算法。

阅读全文 »

写在前面

假如有一个由若干村庄组成的小镇,现在需要修建一条能够连接所有村庄的路,如何才能在达到目的的条件下使修路的成本最小?这个问题实际上就是图的最小生成树(MinimumSpanningTree)问题。

阅读全文 »

写在前面

打开高德地图,查找从A地点到B地点的地铁线路图时,结果页面会有“时间最短”,“价格最低”,“步行最少”等选项。如果把地铁站点看作图的顶点,地铁站之间的连接看作边并且边的权重是地铁经过这条边时需要的时间或者票价的话,就可以把地铁线路的查找抽象为一个图的最短路径问题。
即:在网络(带权图)中,求两个不同顶点之间的所有路径中,边的权值和最小的那条路径。这条路径就叫最短路径(Shortest Path),这条路径的起点叫做源点(Source),路径的最后一个顶点叫做终点(Destination)
最短路径问题不是一个孤立的问题,它是一系列问题的集合,可以分为单源最短路径问题多源最短路径问题

阅读全文 »

巴芬岛附近的一群独角鲸,加拿大努纳武特 (© Eric Baccega/Minden Pictures)

阅读全文 »

写在前面

图的遍历就是把图中的每个顶点不重复地访问一遍,它可以用来解决很多图的问题。

阅读全文 »

写在前面

现实世界中很多事物往往不是线性的一对一关系,还有许多问题是多对多的关系。如地图,互联网等等,为了抽象表示这些关系以便于处理这些网状拓扑的问题,聪明的科学家发明了(Graph)这种数据结构。

阅读全文 »