知识卡片

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

图用顶点记录内嵌邻接集合

理解等级:中级

本章AdjList由vertex数据地址和Set adjacent组成;Graph内嵌一条List adjlists保存各AdjList记录,并另存vcount/ecount及match/destroy。顶点记录与邻居集合是不同两层,邻居项只是借用目标顶点数据地址。

结构图:

classDiagram
class AdjList {
 void* vertex
 Set adjacent
}
class Graph {
 int vcount
 int ecount
 int (*match)(const void* a, const void* b)
 void (*destroy)(void* data)
 List adjlists
}
class List
class Set["Set(List别名)"]
class GraphAPI["图公开函数组(非类型)"] {
 graph_init(Graph* graph, match, destroy) void
 graph_destroy(Graph* graph) void
 graph_ins_vertex(Graph* graph, const void* data) int
 graph_ins_edge(Graph* graph, const void* from, const void* to) int
 graph_rem_vertex(Graph* graph, void** data) int
 graph_rem_edge(Graph* graph, void* from, void** to) int
 graph_adjlist(const Graph* graph, const void* data, AdjList** out) int
 graph_is_adjacent(const Graph* graph, const void* from, const void* to) int
}
Graph *-- List : 内嵌adjlists
List --> AdjList : 元素data指向记录
AdjList *-- Set : 内嵌adjacent
Set ..> List : typedef别名,非继承
GraphAPI ..> Graph : 维护两层关系与计数

init回调按字段同型函数指针简写。VertexColor另定义white/gray/black供搜索算法使用,并不是Graph或AdjList未列出的额外字段;具体搜索顶点会单独保存颜色。

190及02934 graph_init写vcount/ecount=0、match/destroy,list_init(&adjlists,NULL)。外层链不自动销毁数据,专用graph_destroy负责逐记录清理;固定字段步骤O(1)。

198与02932三个宏为&(graph->adjlists)、vcount、ecount字段访问;02933–02938全部graph.c已读,覆盖初始化/销毁/顶点与边变更/查询全部函数。边集合以NULL回调借用目标对象,所有成功计数变更按返回值发生。

201外层链支持动态顶点记录,内层Set表达无序且不重复的邻居。作者对外层不用Set的偏好不等于链表查找在渐近上更快:本章Set也以List实现,二者都可能线性定位。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      Adjlist表示(见示例11-1)。该结构体包含前文刚提到过的两个成员。每个顶点的邻接表实现为一个集合(见第7章),这么做的原因我们会在本章末尾的问与答中给出解释。结构体Graph代表图这种数据结构(见示例11-1)。这个结构体由5个成员组成:vcount代表图中顶点的个数,ecount代表图中边

    • · 查看原书依据

      初始化邻接表链表结构。 graph_init的时间复杂度是的O(1),因为初始化图的所有步骤都能在恒定的时间内完成。

    • · 查看原书依据

      访问和测试结构体Graph中成员的接口。 这些宏的时间复杂度都是O(1)。因为访问结构体中成员的操作都能够在恒定的时间内完成。 示例11-2:抽象数据类型图的实现

    • · 查看原书依据

      集合来表示邻接表,因为邻接表包含的顶点是无序的,而且针对邻接表的主要操作(插入、移除顶点与检测成员关系)非常适合于前面章节中给出的集合这种抽象数据类型。也许邻接表结构链表也应该用集合来实现,但这种方案被否决了,因为这里对邻接表结构链表的主要操作是找出特定顶点的邻接表,链表在这种情况下比集合更适合。

    参考来源

    - 位置:《算法精解:C语言描述》第11章《图的实现与分析》(spine1323;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1290.html;u189-ch11-018)。 - 结论依据:189全部正文和02931–02932完整graph.h实读;Graph五字段、AdjList两字段、枚举和实际API逐项核对,不添加图结构未有的color字段。 - 原始内容:Adjlist表示(见示例11-1)。该结构体包含前文刚提到过的两个成员。每个顶点的邻接表实现为一个集合(见第7章),这么做的原因我们会在本章末尾的问与答中给出解释。结构体Graph代表图这种数据结构(见示例11-1)。这个结构体由5个成员组成:vcount代表图中顶点的个数,ecount代表图中边 - 位置:《算法精解:C语言描述》第11章《graph_init》(spine1323;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1290.html;u190-ch11-018)。 - 结论依据:190及02934 graph_init写vcount/ecount=0、match/destroy,list_init(&adjlists,NULL)。外层链不自动销毁数据,专用graph_destroy负责逐记录清理;固定字段步骤O(1)。 - 原始内容:初始化邻接表链表结构。 graph_init的时间复杂度是的O(1),因为初始化图的所有步骤都能在恒定的时间内完成。 - 位置:《算法精解:C语言描述》第11章《graph_adjlists、graph_vcount、graph_ecount》(spine1331;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1298.html;u198-ch11-018)。 - 结论依据:198与02932三个宏为&(graph->adjlists)、vcount、ecount字段访问;02933–02938全部graph.c已读,覆盖初始化/销毁/顶点与边变更/查询全部函数。边集合以NULL回调借用目标对象,所有成功计数变更按返回值发生。 - 原始内容:访问和测试结构体Graph中成员的接口。 这些宏的时间复杂度都是O(1)。因为访问结构体中成员的操作都能够在恒定的时间内完成。 示例11-2:抽象数据类型图的实现 - 位置:《算法精解:C语言描述》第11章《问与答》(spine1334;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1301.html;u201-ch11-018)。 - 结论依据:201外层链支持动态顶点记录,内层Set表达无序且不重复的邻居。作者对外层不用Set的偏好不等于链表查找在渐近上更快:本章Set也以List实现,二者都可能线性定位。 - 原始内容:集合来表示邻接表,因为邻接表包含的顶点是无序的,而且针对邻接表的主要操作(插入、移除顶点与检测成员关系)非常适合于前面章节中给出的集合这种抽象数据类型。也许邻接表结构链表也应该用集合来实现,但这种方案被否决了,因为这里对邻接表结构链表的主要操作是找出特定顶点的邻接表,链表在这种情况下比集合更适合。