知识卡片
算法结果列表借用原图顶点
mst(graph,start,span,match)成功返回0、失败−1。它改变原图顶点的color/key/parent,span保存实际MstVertex指针,list_destroy只释放该列表容器;需要span及父指针时必须保持原图顶点数据存活。
parent是树父顶点,不保证是span列表的前一个元素,也不保证位于其之前。03078输出顺序a,b,c,d,e,f中b.parent=c、e.parent=f,直接给出父项在后方的例子;应沿parent关系读取树,而不是把列表顺序当拓扑序。
边权通过data2所携带的weight表示,对同一顶点的不同入边要保留各自边权对象;canonical顶点保存全局算法状态。两种角色用相同结构体也不能随意共用会被覆盖的同一weight字段。
298⁄03084 shortest返回0或−1,paths借用图中的PathVertex,调用list_destroy释放列表而非图顶点。parent指向路径中的前一顶点,不保证在列表顺序更早:03085输出b在f之前但b.parent=f。图必须在paths及其顶点引用使用期间保持有效。
303⁄03094 tsp(vertices,start,tour,match)返回0或−1;tour元素借用vertices中的TspVertex,必须保持原始顶点有效。成功路线按顺序排列并在末尾再次引用起点;list_destroy释放tour容器,不释放借用顶点。
315⁄03110 cvxhull(const List *P,List *polygon)成功0失败−1,polygon存放输入P中的Point指针,使用结果时点对象须保持有效,list_destroy只销毁结果列表容器;该接口仅看x、y,不计算三维凸包。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 算法结果列表借用原图顶点
- · 最短路径的接口定义
- · 旅行商问题的接口定义
- · 凸包的接口定义
原书出处 · 4 处
- · 查看原书依据
内存空间有效。一旦不再使用span,就调用list_destroy销毁span。 复杂度 O(EV2),其中V是图中顶点的个数,E是边的条数。但是,如果对此处展示的算法实现进行一点儿改进,其复杂度可达到O(ElgV)(见本章末尾的相关章节)。
- · 查看原书依据
内存空间有效。一旦不再使用paths,就调用list_destroy销毁paths。 复杂度 O(EV2),其中V是图中顶点的个数,E是边的数目。但是,如果对此处展示的算法实现进行一些改进(类似本章末尾对Prim算法的讨论),其复杂度可降低到O(ElgV)(见本章末尾的相关章节)。
- · 查看原书依据
内存空间有效。如果不再使用tour,那么可以调用list_destroy来销毁tour。 复杂度 O(V2),其中V是路线中要访问顶点的个数。
- · 查看原书依据
存储空间就要是有效合法的。一旦不再需要,可以调用list_destroy来销毁polygon。 复杂度 O(nh),这里n表示点集中总的元素个数,h表示凸包中点的个数。