数据结构_树_图_总结

数据结构 - 树、图 总结

数据结构:树(Tree)

二叉树

  1. 二叉树第 i 层的节点数目最多为2 ^ (i - 1) ( i >=1)

  2. 深度为 k 的二叉树最多有(2 ^ k)- 1个节点 (k >= 1)

  3. 在任意一个二叉树中 N0 表示 度数为0的节点个数, N2 表示度数为2的节点个数, 则有 N0 = N2 + 1

满二叉树:一个填满的二叉树

完全二叉树:满二叉树数完全二叉树, 完全二叉树不一定是满二叉树。

二叉树的遍历:先序,中序,后序 树的遍历和代码实现

线索二叉树 线索二叉树

树与二叉树的转换

森林、树与二叉树相互转换

哈弗曼树、编码

哈夫曼树 哈夫曼树结构和带权路径长度计算

哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度

平衡二叉树

参考自: 平衡二叉树(树的旋转) 以下是节选内容

数据结构_树_图_总结

数据结构:图(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 + E)O(V^2)
添加顶点O(1)O(V^2)
添加边O(1)O(1)
检查相邻性O(V)O(1)

“检查相邻性” 是指对于给定的顶点,尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V),因为最坏的情况是一个顶点与每一个顶点都相连。

稀疏图的情况下,每一个顶点都只会和少数几个顶点相连,这种情况下相邻列表是最佳选择。如果这个图比较密集,每一个顶点都和大多数其他顶点相连,那么相邻矩阵更合适。

最小生成树

参考自: 最小生成树的两种方法(Kruskal算法和Prim算法) ,以下是节选部分内容

最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树

数据结构_树_图_总结

Kruskal算法

此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。

  1. 把图中的所有边按代价从小到大排序;
  2. 把图中的n个顶点看成独立的n棵树组成的森林;
  3. 按权值从小到大选择边,所选的边连接的两个顶点ui,vi ui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。
  4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
数据结构_树_图_总结

Prim算法

此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。

  1. 图的所有顶点集合为VV;初始令集合u={s},v=V?uu={s},v=V?u;
  2. 在两个集合u,vu,v能够组成的边中,选择一条代价最小的边(u0,v0)(u0,v0),加入到最小生成树中,并把v0v0并入到集合u中。
  3. 重复上述步骤,直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合u中加点,所以最小代价边必须同步更新;需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息,:

数据结构_树_图_总结

最短路径

请观看视频讲解 这个视频对于原理讲解得已近足够清除。

关键路径

参考博客 ?数据结构 图之关键路径