知识卡片
图算法状态各有距离含义
MstVertex的key表示从当前生成树接入该顶点的候选边权;PathVertex的d表示从源到该点的路径长度估计;TspVertex保存平面坐标供该例选择路线。前两者虽同有data/weight/color/parent,也不是同一算法状态或继承类型。
结构图
classDiagram
class MstVertex {
void* data
double weight
VertexColor color
double key
MstVertex* parent
}
class PathVertex {
void* data
double weight
VertexColor color
double d
PathVertex* parent
}
class TspVertex {
void* data
double x
double y
VertexColor color
}
class GraphAlgorithms {
<<非类型>>
mst(graph, start, span, match) int
shortest(graph, start, paths, match) int
tsp(vertices, start, tour, match) int
}
MstVertex --> MstVertex : parent
PathVertex --> PathVertex : parent
GraphAlgorithms ..> MstVertex
GraphAlgorithms ..> PathVertex
GraphAlgorithms ..> TspVertex
函数组是自由函数展示,字段weight在邻接边数据中表达该边权;不可让同一全局顶点对象的一个weight字段同时冒充全部入边权。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
头文件。 本章内容包括: 最小生成树 树可以看做许多相关联问题的抽象模型。最小生成树能用最小的代价将一个无方向的带权图的所有顶点连接起来。 最短路径 它是解决各类最短路径问题的结果。最短路径是连接一个有方向的带权图中两个顶点之间代价最小的路径。 旅行商问题 它是一个非常难以解决的问题,在此问题中,要
参考来源
- 位置:《算法精解:C语言描述》第16章《第16章 图算法》(spine1409;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1375.html;u291-ch16-002)。
- 结论依据:291/03074–03075 graphalg.h全部字段/原型实读,MST状态与边数据角色由已读295说明,未预宣称后续全部算法已生成。
- 原始内容:头文件。 本章内容包括: 最小生成树 树可以看做许多相关联问题的抽象模型。最小生成树能用最小的代价将一个无方向的带权图的所有顶点连接起来。 最短路径 它是解决各类最短路径问题的结果。最短路径是连接一个有方向的带权图中两个顶点之间代价最小的路径。 旅行商问题 它是一个非常难以解决的问题,在此问题中,要