知识卡片
图用顶点记录内嵌邻接集合
本章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:抽象数据类型图的实现
- · 查看原书依据
集合来表示邻接表,因为邻接表包含的顶点是无序的,而且针对邻接表的主要操作(插入、移除顶点与检测成员关系)非常适合于前面章节中给出的集合这种抽象数据类型。也许邻接表结构链表也应该用集合来实现,但这种方案被否决了,因为这里对邻接表结构链表的主要操作是找出特定顶点的邻接表,链表在这种情况下比集合更适合。