知识卡片
邻接定位成本会放大搜索开销
标准邻接表BFS/DFS若可直接定位每个邻接顶点对应的记录,常见遍历成本为O(V+E)。但本章具体实现每扫一条邻接项,就调用graph_adjlist从顶点记录链中线性查找,单次最坏O(V)。
因此本例完整遍历可有O(V+VE)上界,而不是仅凭每条边看一次就推出O(V+E)。BFS若只到达部分图,也应按所扫描边的数量计入定位开销;初始化和结果收集仍需全顶点扫描。
若要恢复直接访问记录的成本,可考虑索引或在邻接项保存可用记录引用,但需重新管理引用稳定性与变更维护。本书未实现这些改动,本卡未测量实际速度。
200与02947 dfs_main对每条邻接边调用graph_adjlist,线性定位最坏O(V),所以此具体实现全图可O(V+VE),不能照搬正文O(V+E)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
bfs的时间复杂度为O(V+E),这里V是图中顶点的个数,E是边的个数。这是因为初始化顶点的颜色属性以及确保起始结点存在都需要O(V)的运行时间,广度优先搜索中的循环的复杂度是O(V+E),加载跳数统计链表的时间是O(V)。 示例11-3:广度优先搜索的头文件 示例11-4:广度优先搜索的实现
- · 查看原书依据
O(V+E),这里V代表图中顶点的个数,而E代表边的个数。这是因为初始化顶点的颜色信息需要O(V)的时间,而dfs_main的时间复杂度为O(V+E)。 示例11-5:深度优先搜索的头文件 示例11-6:深度优先搜索的函数实现
参考来源
- 位置:《算法精解:C语言描述》第11章《关于图的应用举例:计算网络跳数》(spine1332;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1299.html;u199-ch11-021)。
- 结论依据:199完整复杂度说明与02943每个member调用graph_adjlist、196该函数线性查链实读;200的02947 dfs_main相同内层调用已读,成本按实际嵌套组成而非照表。
- 原始内容:bfs的时间复杂度为O(V+E),这里V是图中顶点的个数,E是边的个数。这是因为初始化顶点的颜色属性以及确保起始结点存在都需要O(V)的运行时间,广度优先搜索中的循环的复杂度是O(V+E),加载跳数统计链表的时间是O(V)。 示例11-3:广度优先搜索的头文件 示例11-4:广度优先搜索的实现
- 位置:《算法精解:C语言描述》第11章《关于图的应用举例:拓扑排序》(spine1333;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1300.html;u200-ch11-021)。
- 结论依据:200与02947 dfs_main对每条邻接边调用graph_adjlist,线性定位最坏O(V),所以此具体实现全图可O(V+VE),不能照搬正文O(V+E)。
- 原始内容:O(V+E),这里V代表图中顶点的个数,而E代表边的个数。这是因为初始化顶点的颜色信息需要O(V)的时间,而dfs_main的时间复杂度为O(V+E)。 示例11-5:深度优先搜索的头文件 示例11-6:深度优先搜索的函数实现