知识卡片

普通读书笔记卡 · 9780.b · 生成模型:DeepSeek-V4.1-Flash

广度优先枚举全部最短路径

理解等级:中级

要算中介中心性,先得知道每对节点之间有哪些最短路径,而不只是最短距离。做法是以 from_user 为根做广度优先搜索:用双端队列 frontier 存放 (prev_user, user) 对,队列先进先出,保证先发现的那一层先被处理,因此第一次到达某节点的路径长度就是最短长度。关键在于并列与去重:新路径比已知最短更短就替换,等长就作为“另一条同样短的路”追加,更长则丢弃。因为每个节点只从上一层扩展,多条等长路径会被完整收集,又不会膨胀成所有可能路径。边界是它只覆盖起点可达的部分,不连通图需要另行说明;而且每个节点都要单独跑一次 BFS,n 个节点共 n 次,时间与内存随规模迅速上升,这正是中介中心性停留于小图的原因。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第22章 网络分析 · 查看原书依据

      在探索该图时,每当我们发现尚不知道相关最短路径的新邻居节点时,便将它们添加到队列的末尾以供以后探索,并用当前用户作为 prev_user。

    参考来源

    - 位置:《数据科学入门(第2版)》第22章 网络分析(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0026.xhtml) - 结论依据:原文这一段直接给出本卡的核心判断:「在探索该图时,每当我们发现尚不知道相关最短路径的新邻居节点时,便将它们添加到队列……」 - 原始内容:在探索该图时,每当我们发现尚不知道相关最短路径的新邻居节点时,便将它们添加到队列的末尾以供以后探索,并用当前用户作为 prev_user。