知识卡片

操作参考卡 · 5654.d.1.f.3.o · 生成模型:未记录

邻接查询返回图内借用视图

理解等级:中级

graph_adjlist(const Graph,const void,AdjList**)按顶点查找并交回图内AdjList地址,成功0、失败-1;它不是复制。graph_adjlists实际宏返回&graph->adjlists,即List*,与接口图写List返回值不同,遍历时不能任意改动底层链破坏图状态。

graph_is_adjacent(const Graph,const void,const void*)回答第二顶点是否在第一顶点的出邻居集合中,1真0假;它不是任意路径可达查询。graph_vcount/ecount读取维护计数,字段访问O(1),而按顶点定位邻接记录要在链中扫描,最坏O(|V|)。

这些返回地址只在相关图结构/数据保持有效时可使用,查询成功没有交接销毁权,也不提供并发修改保护。

196及02937 graph_adjlist按match命中后*adjlist=list_data(element),不是结构体复制。最坏O(V),额外声明/更新的prev并不参与结果;不因局部字段返回而误判整个定位常数时间。

197与02938 graph_is_adjacent实际查询方向是data1→data2,尽管正文首句表述易倒置。源不存在return0,否则返回set_is_member;未逐层搜索可达路径。外层扫描与目标集合扫描的总上界O(V),假定普通无重复邻接/常数判等。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      graph_adjlist 返回值 如果取得邻接表成功,返回0;否则返回-1。 描述 取出graph中由data所指定的顶点的邻接表。返回的邻接表以结构体AdjList的形式保存,该结构体包含与data相匹配的顶点,以及其他与其邻接的顶点。函数返回后得到一个指向邻接表的指针,因此调用者必须保证不修改

    • · 查看原书依据

      检索邻接表结构链表,直到找到其中包含指定顶点的那个AdjList结构体。 graph_adjlist操作的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为检索邻接表结构链表是复杂度为O(V)的操作。

    • · 查看原书依据

      data2是否在data1的邻接表中。 graph_is_adjacent的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为检索邻接表结构链表以及对set_is_member的调用都是复杂度为O(V)的操作。

    参考来源

    - 位置:《算法精解:C语言描述》第11章《图的接口定义》(spine1322;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1289.html;u188-ch11-016)。 - 结论依据:188四类查询和计数宏全部说明/02926–02930原型及02932实际宏、02937–02938代码实读,明确List*实际地址与借用期限。 - 原始内容:graph_adjlist 返回值 如果取得邻接表成功,返回0;否则返回-1。 描述 取出graph中由data所指定的顶点的邻接表。返回的邻接表以结构体AdjList的形式保存,该结构体包含与data相匹配的顶点,以及其他与其邻接的顶点。函数返回后得到一个指向邻接表的指针,因此调用者必须保证不修改 - 位置:《算法精解:C语言描述》第11章《graph_adjlist》(spine1329;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1296.html;u196-ch11-016)。 - 结论依据:196及02937 graph_adjlist按match命中后*adjlist=list_data(element),不是结构体复制。最坏O(V),额外声明/更新的prev并不参与结果;不因局部字段返回而误判整个定位常数时间。 - 原始内容:检索邻接表结构链表,直到找到其中包含指定顶点的那个AdjList结构体。 graph_adjlist操作的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为检索邻接表结构链表是复杂度为O(V)的操作。 - 位置:《算法精解:C语言描述》第11章《graph_is_adjacent》(spine1330;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1297.html;u197-ch11-016)。 - 结论依据:197与02938 graph_is_adjacent实际查询方向是data1→data2,尽管正文首句表述易倒置。源不存在return0,否则返回set_is_member;未逐层搜索可达路径。外层扫描与目标集合扫描的总上界O(V),假定普通无重复邻接/常数判等。 - 原始内容:data2是否在data1的邻接表中。 graph_is_adjacent的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为检索邻接表结构链表以及对set_is_member的调用都是复杂度为O(V)的操作。