知识卡片
搜索状态包在顶点数据中
图的基本结构不直接存搜索颜色。本例把应用数据包进BfsVertex或DfsVertex,再将包装地址作为Graph顶点保存;match只比较包装内data,让颜色/跳数变化不改变顶点身份。
结构图:
classDiagram
class BfsVertex {
void* data
VertexColor color
int hops
}
class DfsVertex {
void* data
VertexColor color
}
class Graph
class VertexColor {
<<enumeration>>
white
gray
black
}
class SearchAPI["搜索函数组(非类型)"] {
bfs(Graph* graph, BfsVertex* start, List* hops) int
dfs(Graph* graph, List* ordered) int
}
Graph --> BfsVertex : BFS用作vertex数据
Graph --> DfsVertex : DFS用作vertex数据
BfsVertex --> VertexColor : color
DfsVertex --> VertexColor : color
SearchAPI ..> Graph : 修改搜索状态
两种包装是不同示例的数据形状,图不表示同一Graph顶点必须同时属于两种类型。bfs的hops结果和dfs的ordered只借用图内包装地址,销毁结果链不能同时释放仍在图中的对象。
200与02946 DfsVertex只有data/color,dfs修改color,ordered保存图内对象地址并以NULL销毁回调建链。失败时销毁部分列表节点,不回滚图颜色;借用数据须保持有效。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
BfsVertex类型的结构体(见示例11-3),该结构体有3个成员:data是指向图中顶点的数据域的指针,color在搜索过程中维护顶点的颜色,hops维护从起始结点开始到顶点的跳数统计。match函数是由调用者在初始化graph时作为参数传给graph_init的。match应该只对BfsVer
- · 查看原书依据
DfsVertex结构体(见示例11-5),该结构体拥有两个成员:data是指向顶点数据域部分的指针,而color在搜索过程中负责维护顶点的颜色信息。match函数是由调用者在初始化graph时通过参数传递给graph_init的,该函数应该只对DfsVertex结构体中的data成员进行比较。 d
参考来源
- 位置:《算法精解:C语言描述》第11章《关于图的应用举例:计算网络跳数》(spine1332;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1299.html;u199-ch11-020)。
- 结论依据:199完整BfsVertex与match说明、02940–02941头文件及200/02946实际DfsVertex两字段/dfs原型实读,graph.h颜色枚举已读;无虚构继承关系。
- 原始内容:BfsVertex类型的结构体(见示例11-3),该结构体有3个成员:data是指向图中顶点的数据域的指针,color在搜索过程中维护顶点的颜色,hops维护从起始结点开始到顶点的跳数统计。match函数是由调用者在初始化graph时作为参数传给graph_init的。match应该只对BfsVer
- 位置:《算法精解:C语言描述》第11章《关于图的应用举例:拓扑排序》(spine1333;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1300.html;u200-ch11-020)。
- 结论依据:200与02946 DfsVertex只有data/color,dfs修改color,ordered保存图内对象地址并以NULL销毁回调建链。失败时销毁部分列表节点,不回滚图颜色;借用数据须保持有效。
- 原始内容:DfsVertex结构体(见示例11-5),该结构体拥有两个成员:data是指向顶点数据域部分的指针,而color在搜索过程中负责维护顶点的颜色信息。match函数是由调用者在初始化graph时通过参数传递给graph_init的,该函数应该只对DfsVertex结构体中的data成员进行比较。 d