【】chapter贪婪算法.ppt

数据结构与算法 Chapter13 贪婪算法 内容提要 13.1 示例问题提出 13.2 贪婪算法的思想 13.3 贪婪算法的应用 货箱装船 拓扑排序 单源最短路径 最小耗费生成树 2、单源点最短路径 边上权值非负情形的单源最短路径问题 单源最短路径示例：源点1 如何求从某一源点到各个终点的路径 ? Dijkstar算法的贪婪准则 算法实现：最短路径的存储 利用数组 p，前驱顶点 p[i]给出从s到达i的路径中顶点i前面的那个顶点。 从s到顶点i的路径可反向创建：从i出发按照p[i], p[p[i]], p[p[p[i]]], …的顺序，直到到达顶点s或0。 辅助数组d[i]：顶点当前最短路径长度 辅助数组d[i]的变化 L表 源点未到达顶点表 采用数据结构： 无序链表 VS. 最小堆 初始值： 与源点邻接的顶点链表 更新情况： 某个顶点j的d[j]发生变化，且不在L中，则加入到链表中 Dijkstar算法伪代码 Dijkstar算法（程序13-5） Dijkstar算法复杂度分析 对于具有n个顶点和e条边的带权有向图， 无论采用邻接矩阵，还是邻接链表，时间复杂度均为O(n2) 原因：必须至少对每一条边检查一次！ 邻接矩阵仅能优化最后一个循环 O(e) 【思考】如何求所有顶点之间的最短路径 3、最小生成树 生成树的特点 生成树的类型 最小耗费（代价）生成树及构造原则 最小耗费生成树构造方法 （1）Kruskal算法 Kruskal算法思想 Kruskal算法示例 Kruskal算法伪码描述 利用最小堆和并查集实现Kruskal算法 补充：集合的树形表示方法 并查集 (Union-Find Sets) class UnionFind { public: UnionFind(int Size = 10); ~UnionFind() { delete [] parent; delete [] root; } void Union(int, int); int Find(int); private: int *parent; 保存该树中节点的个数 bool *root; 根节点标志 }; UnionFind::UnionFind(int n) { //初始化，一个元素作为一类或一棵树 root = new bool[n+1]; parent = new int[n+1]; for (int e = 1; e = n; e++) { parent[e] = 1; 节点个数为1 root[e] = true; 为根节点 } } void UnionFind::Union(int i, int j) { if (parent[i] parent[j]) { 将i作为j的子树 parent[j] += parent[i]; root[i] = false; parent[i] = j; } else { 将j作为i的子树 parent[i] += parent[j]; root[j] = false; parent[j] = i; } } int UnionFind::Find(int e) { int j = e; while (!root[j]) j = parent[j]; 找到包含e的树的根 int f = e; while (f != j) { int pf = parent[f]; parent[f] = j; f = pf; } return j; } 边节点定义 template class T class EdgeNode { friend ostream operator(ostream, EdgeNodeT); friend UNetworkT; friend void main(void); public: operator T () const { return weight; } private: T weight; // 边上权值 int u, v; // 边的起点、终点号 }; templateclass T ostream operator(ostream out, EdgeNodeT x) {