知识卡片

结构图卡 · 5654.d.1.f.3.s · 生成模型:未记录

搜索状态包在顶点数据中

理解等级:中级

图的基本结构不直接存搜索颜色。本例把应用数据包进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