algorithm - 与肯汤普森的六度分离

Question

我目前正在开展一个项目，我需要与 Ken Thompson 一起实现六度分离，他和他的同事 Dennis Ritchie 创建了 UNIX 操作系统。我想问一下，为图表选择什么标准更好？就像《六度的凯文培根》，我们选择的艺术家是和他一起出演过电影的艺术家。六度肯汤普森怎么样，我应该用和他有关系的吗？

而且，Dijkstra 的最短路径是解决这个问题的更好方法吗？还是深度优先搜索更好的方法？

标签： algorithmgraph-theorygraph-algorithm

Answer 1

不是深度优先，而是广度优先搜索 ( BFS ) 可能是确定某人“内圈”的最有效方法。

如果您想显示两个已知人的最多六级分离，您也可以尝试双向 BFS

关于“谁与 Ken Thompson 有关系”的问题非常具有哲理……您需要自己定义条件 - 也许您可以揭示同一所学校的学生、同一所大学的学生和教师、亲戚、同事、所有 UNIX 用户和C 程序员 ;), ...也许没有。