数据结构:树(Tree)二叉树
满二叉树:一个填满的二叉树 完全二叉树:满二叉树数完全二叉树, 完全二叉树不一定是满二叉树。 二叉树的遍历:先序,中序,后序 树的遍历和代码实现 线索二叉树 线索二叉树树与二叉树的转换哈弗曼树、编码
平衡二叉树参考自: 平衡二叉树(树的旋转) 以下是节选内容 数据结构:图(Graph)紧接矩阵与邻接表参考自: 数据结构:图(Graph) , 以下是节选部分内容 邻接表 在邻接列表实现中,每一个顶点会存储一个从它这里开始的边的列表。比如,如果顶点A 有一条边到B、C和D,那么A的列表中会有3条边 邻接列表只描述了指向外部的边。A 有一条边到B,但是B没有边到A,所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时,因为遍历邻接列表直到找到为止。 邻接矩阵 在邻接矩阵实现中,由行和列都表示顶点,由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如,如果从顶点A到顶点B有一条权重为 5.6 的边,那么矩阵中第A行第B列的位置的元素值应该是5.6: 往这个图中添加顶点的成本非常昂贵,因为新的矩阵结果必须重新按照新的行/列创建,然后将已有的数据复制到新的矩阵中。 所以使用哪一个呢?大多数时候,选择邻接列表是正确的。下面是两种实现方法更详细的比较。 假设 V 表示图中顶点的个数,E 表示边的个数。
“检查相邻性” 是指对于给定的顶点,尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V),因为最坏的情况是一个顶点与每一个顶点都相连。 在 稀疏图的情况下,每一个顶点都只会和少数几个顶点相连,这种情况下相邻列表是最佳选择。如果这个图比较密集,每一个顶点都和大多数其他顶点相连,那么相邻矩阵更合适。 最小生成树参考自: 最小生成树的两种方法(Kruskal算法和Prim算法) ,以下是节选部分内容 最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树 Kruskal算法 此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
Prim算法 此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。
由于不断向集合u中加点,所以最小代价边必须同步更新;需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息,: 最短路径请观看视频讲解 这个视频对于原理讲解得已近足够清除。 关键路径参考博客 数据结构 图之关键路径 来源:https://www./content-4-695601.html |
|