策略和技术

图的存储结构(邻接表)- 数据结构和算法57

图的存储结构(邻接表)让编程改变世界Change the world by program邻接表(无向图)邻接矩阵看上去是个不错的选择,首先是容易理解,第二是索引和编排都很舒服~但是我们也发现,对于边数相对顶点较少的图,这种结构无疑是存在对存储空间的极大浪费。邻接表(有向图)因此我们可以考虑另外一种存储结构方式,例如把数组与链表结合一起来存储,这种方式在图结构也

图的存储结构(邻接矩阵)- 数据结构和算法56

图的存储结构(邻接矩阵)让编程改变世界Change the world by program图的存储结构图的存储结构相比较线性表与树来说就复杂很多。我们回顾下,对于线性表来说,是一对一的关系,所以用数组或者链表均可简单存放。树结构是一对多的关系,所以我们要将数组和链表的特性结合在一起才能更好的存放。那么我们的图,是多对多的情况,另外图上的任何一个顶点都可以被看作

图的遍历(深度优先遍历)- 数据结构和算法59

图的遍历(深度优先遍历)让编程改变世界Change the world by program图的遍历树的遍历我们谈了四种方式,大家回忆一下,树因为根结点只有一个,并且所有的结点都只有一个双亲,所以不是很难理解。但是谈到图的遍历,那就复杂多了,因为它的任一顶点都可以和其余的所有顶点相邻接,因此极有可能存在重复走过某个顶点或漏了某个顶点的遍历过程。对于图的遍历,如果

马踏棋盘算法(骑士周游问题)- 数据结构和算法60

马踏棋盘算法(骑士周游问题)让编程改变世界Change the world by program马踏棋盘算法(骑士周游问题)题目渊源:马踏棋盘问题(又称骑士周游或骑士漫游问题)是算法设计的经典问题之一。题目要求:国际象棋的棋盘为8*8的方格棋盘,现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋

图的存储结构(十字链表、邻接多重表、边集数组)- 数据结构和算法58

图的存储结构(十字链表、邻接多重表、边集数组)让编程改变世界Change the world by program十字链表邻接表固然优秀,但也有不足,例如对有向图的处理上,有时候需要再建立一个逆邻接表~那我们思考了:有没有可能把邻接表和逆邻接表结合起来呢?答案是肯定的,这就是我们现在要谈的十字链表(Orthogonal List)为此我们重新定义顶点表结点结构

图的遍历(广度优先遍历)- 数据结构和算法61

图的遍历(广度优先遍历)让编程改变世界Change the world by program广度优先遍历广度优先遍历(BreadthFirstSearch),又称为广度优先搜索,简称BFS。如果以之前我们找钥匙的例子来讲,运用深度优先遍历意味着要先彻底查找完一个房间再开始另一个房间的搜索。但我们知道,钥匙放在沙发地下等犄角旮旯的可能性极低,因此我们运用新的方案:

最小生成树(克鲁斯卡尔算法)- 数据结构和算法63

最小生成树(克鲁斯卡尔算法)让编程改变世界Change the world by program克鲁斯卡尔算法无论是普里姆算法(Prim)还是克鲁斯卡尔算法(Kruskal),他们考虑问题的出发点都是:为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能的小。普里姆算法是以某顶点为起点,逐步找各个顶点上最小权值的边来构建最小生成树的。现在我们换一

最小生成树(普里姆算法)- 数据结构和算法62

最小生成树(普里姆算法)让编程改变世界Change the world by program最小生成树小苍童鞋的难题:普里姆算法方案一最小生成树成本:11+26+20+22+18+21+24+19=161方案二最小生成树成本:11+26+20+22+18+21+24+19=161方案三最小生成树成本:11+26+20+22+18+21+24+19=161

最短路径(迪杰斯特拉算法)- 数据结构和算法64

最短路径(迪杰斯特拉算法)让编程改变世界Change the world by program最短路径(迪杰斯特拉算法)我们时常会面临着对路径选择的决策问题,例如在中国的一些一线城市如北京、上海、广州、深圳等,一般从A点到到达B点都要通过几次地铁、公交的换乘才可以到达。有些朋友想用最短对的时间,有些朋友想花最少的金钱,这就涉及到不同的方案,那么如何才能最快的计算出

最短路径(弗洛伊德算法)- 数据结构和算法65

最短路径(弗洛伊德算法)让编程改变世界Change the world by program最短路径(弗洛伊德算法)迪杰特斯拉算法对比弗洛伊德算法迪杰特斯拉算法对比弗洛伊德算法那我们为嘛还有讲它的必要呢?因为迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径,但弗洛伊德算法是求所有顶点到所有顶点的最短路径。弗洛伊德算法非常简洁优雅。为了能讲明白弗洛伊德算法的精