知识卡片
删顶点先清空所有入出边
本实现不提供自动级联删除顶点。graph_rem_vertex先扫描所有邻接集合,若任何集合仍引用目标就失败;再确认目标顶点存在且自己的邻接集合为空,才移除外层记录并交回vertex数据地址。
这同时排除入边和出边,防止图中留下仍指向已移走顶点的数据引用。移除记录后vcount减少,实际数据不由函数destroy,需调用方按约定管理。不能把“从外层链删一个节点”当整次操作O(1):全图入边检查需O(V+E)模型。
计数/边检查以合法图和一致match为前提;若调用方绕过借用视图直接改链,函数不能替它修复全部被破坏的不变量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
确保该顶点不存在于任何邻接表中,但顶点要存在于邻接表结构链表里,且该顶点的邻接表为空。之后,通过调用list_rem_next从邻接表链表中移除合适的AdjList结构体。最后,使图数据结构的vcount成员递减1,更新图中的顶点计数。 graph_rem_vertex的时间复杂度为O(V+E),这
参考来源
- 位置:《算法精解:C语言描述》第11章《graph_rem_vertex》(spine1327;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1294.html;u194-ch11-019)。
- 结论依据:188顶点移除约定、194全文与02936完整rem_vertex扫描、found/temp/prev、目标空邻接判断和成功输出代码实读,未执行级联删除。
- 原始内容:确保该顶点不存在于任何邻接表中,但顶点要存在于邻接表结构链表里,且该顶点的邻接表为空。之后,通过调用list_rem_next从邻接表链表中移除合适的AdjList结构体。最后,使图数据结构的vcount成员递减1,更新图中的顶点计数。 graph_rem_vertex的时间复杂度为O(V+E),这