北京
前几天我在看《曼达洛人》时突然意识到：我并不认识佩德罗·帕斯卡。这本身就够让人难过的了。 但也许我认识某个人，那个人又认识另一个人，另一个人又认识下一个人……最终，在某个地方，有一条有限的介绍链能把我和他连起来。所以，今天我们要解决的计算机科学问题是：到底需要多少次介绍，才能走到他面前？ 我们无意间发明了一个图论问题。 把地球上的每个人想象成一个节点，任何两个人之间的朋友或熟人关系就是一条边： Alexandra ── Maria ── Sofia ── Pedro │ └── John ── Elena ── Carlos 这是一个无权且无向的图。 无权意味着每条关系的权重都一样：我们不在乎 Maria 是 Sofia 的闺蜜，还是只在咖啡馆见过一面的陌生人。 无向意味着关系是双向的：如果 Alexandra 认识 Maria，那 Maria 也认识 Alexandra。 如果去掉原问题里的花哨包装，它其实就从“我怎么才能见到佩德罗·帕斯卡？”变成了“给定一个无权图，节点 A 到节点 B 的最短路径是什么？”如果你熟悉树或图，就会知道这听起来正是 BFS（广度优先搜索）。 在代码里，表示这种数据最简单的方式是邻接表： const graph = { Alexandra: ["Maria", "John"], Maria: ["Alexandra", "Sofia"], Sofia: ["Maria", "Pedro"], Pedro: ["Sofia"], John: ["Alexandra", "Elena"], Elena: ["John", "Carlos"], Carlos: ["Elena"], }; 把妄想变成算法 很遗憾，对着虚空大喊“有人认识佩德罗·帕斯卡吗？”并不是算法。它没有顺序，没有记忆，也没有停止条件。如果你只是从一个人走到另一个人，谁看起来有趣就找谁，那你可能会原地打转，也可能永远找不到目标。 BFS 的做法完全不同：先从起点出发，检查所有直接认识的人；如果里面没有 Pedro，再检查这些人的朋友；然后再检查朋友的朋友。这样一层一层向外扩展，第一次遇到 Pedro 时走过的路径，就是最短的介绍链。 这就像在社交网络里玩“六度分隔”游戏：你不需要认识大明星，你只需要找到那条最短的熟人链。而 BFS，就是帮你在图里找到这条链的可靠方法。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
