8.1 最小生成树 8.1.1 什么是最小生成树 解决最小生成树有很多算法,但是归结起来都是贪心算法。 贪心算法: 什么是“贪”:每一步都要最好的 什么是“好”:权重最小的边 但是因为是最小生成树,所以这个贪心算法还需要约束: 只能用图里有的边 只能正好用掉 | V | - 1 条边 不能有回路 贪心算法由两个著名的算法:Prim 算法 和 Kruskal 算法。 8.1.2 Prim 算法 Prim 算法–选一个结点,让一棵小树“长大” (和之前 单源最短路径中的 Dijkstra算法很像)(针对的是点) 和 D…

2017年7月10日 0条评论 4点热度 阅读全文

6.1 什么是图 6.1.1 定义 图的定义:表示多对多的关系 抽象数据类型定义 怎么在程序中表示一个图:邻接矩阵和邻接表。 6.1.2 邻接矩阵表示法 定义 邻接矩阵的优点: 邻接矩阵的缺点: C 语言实现 /* 图的邻接矩阵表示法 */ #define MaxVertexNum 100 /* 最大顶点数设为100 */ #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ typedef …

2017年7月10日 0条评论 10点热度 阅读全文

请跟着上一讲 数据结构 学习笔记(四):树(上):树的表示,二分查找,二叉树,先中后层次遍历 继续学习 4.1 二叉搜索树 4.1.1 二叉搜索树及查找 什么是二叉搜索树 回顾上一讲提到的查找问题: 静态查找(集合元素不动,只发生查找操作)和动态查找(集合元素经常动态变化,经常发生插入删除) 针对动态查找,数据如何组织? 静态查找很好的解决方法是二分查找,因为提前有效的组织了数据,使它有序化,使线性的查找过程变成了在类似树中的查找过程,查找效率就是树的高度。 因此,我们想,有没有一种办法。直接把数按照一定的规则放到…

2017年7月9日 0条评论 3点热度 阅读全文