知识卡片

普通读书笔记卡 · 3644.h.4 · 生成模型:未记录

算法结果列表借用原图顶点

理解等级:中级

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表示凸包中点的个数。

    参考来源

    - 位置:《算法精解:C语言描述》第16章《最小生成树的接口定义》(spine1410;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1376.html;u294-ch16-005)。 - 结论依据:294全部接口说明、03077精确原型及已读295/03078完整输出列表实读,纠正正文父项必在前的断言。 - 原始内容:内存空间有效。一旦不再使用span,就调用list_destroy销毁span。 复杂度 O(EV2),其中V是图中顶点的个数,E是边的条数。但是,如果对此处展示的算法实现进行一点儿改进,其复杂度可达到O(ElgV)(见本章末尾的相关章节)。 - 位置:《算法精解:C语言描述》第16章《最短路径的接口定义》(spine1413;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1379.html;u298-ch16-005)。 - 结论依据:298/03084 shortest返回0或−1,paths借用图中的PathVertex,调用list_destroy释放列表而非图顶点。parent指向路径中的前一顶点,不保证在列表顺序更早:03085输出b在f之前但b.parent=f。图必须在paths及其顶点引用使用期间保持有效。 - 原始内容:内存空间有效。一旦不再使用paths,就调用list_destroy销毁paths。 复杂度 O(EV2),其中V是图中顶点的个数,E是边的数目。但是,如果对此处展示的算法实现进行一些改进(类似本章末尾对Prim算法的讨论),其复杂度可降低到O(ElgV)(见本章末尾的相关章节)。 - 位置:《算法精解:C语言描述》第16章《旅行商问题的接口定义》(spine1417;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1383.html;u303-ch16-005)。 - 结论依据:303/03094 tsp(vertices,start,tour,match)返回0或−1;tour元素借用vertices中的TspVertex,必须保持原始顶点有效。成功路线按顺序排列并在末尾再次引用起点;list_destroy释放tour容器,不释放借用顶点。 - 原始内容:内存空间有效。如果不再使用tour,那么可以调用list_destroy来销毁tour。 复杂度 O(V2),其中V是路线中要访问顶点的个数。 - 位置:《算法精解:C语言描述》第17章《凸包的接口定义》(spine1427;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1393.html;u315-ch16-005)。 - 结论依据:315/03110 cvxhull(const List *P,List *polygon)成功0失败−1,polygon存放输入P中的Point指针,使用结果时点对象须保持有效,list_destroy只销毁结果列表容器;该接口仅看x、y,不计算三维凸包。 - 原始内容:存储空间就要是有效合法的。一旦不再需要,可以调用list_destroy来销毁polygon。 复杂度 O(nh),这里n表示点集中总的元素个数,h表示凸包中点的个数。