在1990年代初期,两名大学生发明了一款名为“六度分离”的游戏。该游戏的概念是演员凯文·贝肯可以通过不超过六个步骤与任何其他演员建立联系。为什么是凯文·贝肯?这纯属偶然,但这两名学生注意到贝肯在一次采访中说“他与好莱坞的每个人或者与他们合作过的人合作过”,并将这句话视为挑战。从某个演员到凯文·贝肯的步骤数被称为“贝肯数”。原始的“六度分离”游戏的挑战是仅凭头脑中的知识将两名演员联系起来。现代我们不需要聪明,可以通过结合数据和算法来解决贝肯数问题。数据部分相对简单,互联网电影数据库(IMDB)允许直接下载所需信息。具体来说,我们需要的是演员名称和职位的name.basics.tsv.gz文件,电影名称和日期的title.basics.tsv.gz文件,以及演员和电影之间关系的title.principals.tsv.gz文件。为了使表格更小且函数更快,ETL过程中对原始文件进行了简化,结果是三个较小的表。演员表有371,557行,电影表有678,204行,电影演员表有1,866,533行。计算任何给定演员的贝肯数所需的算法是什么?演员通过电影连接在一起。演员和电影共同形成一个图!演员是图的节点,电影是图的边。幸运的是,PostgreSQL已经有