为了更好地理解这个问题，请注意，这基本上只是未加权的单源最短路径问题，可以使用广度优先搜索来解决。您的问题中的图表定义为：
- 每个节点代表一个作者。
- 两个节点之间存在一条边，当且仅当有一篇论文由两个节点代表的两位作者共同撰写。
对于您的示例，图表如下：
雷西格
|
|
鄂尔多斯——马丁
| /
| /
| /
| /
| /
史密斯——陈
雅布隆斯基——薛
因此，该算法最初将距离 0 分配给鄂尔多斯，将无穷大分配给其他人。然后当它迭代地访问邻居时，它分配的距离越来越大。所以下一次迭代将把距离（或者在这种情况下是 Erdos 数）分配给 Reisig、Martin 和 Smith。下一次也是最后一次迭代将为 Chen 分配距离 2。Jablonski 和 Hsueh 的距离将保持为无穷大。
使用邻接列表的图形表示：
e = 鄂尔多斯
r = Reisig
m = 马丁
s = 史密斯
c = 陈
j = 雅布隆斯基
h = 雪
e: 有效值
回覆
米：es
年代：欧共体
CS
Ĵ：小时
h: j
用Python解决它的代码：
import Queue
def calc_erdos(adj_lst):
erdos_numbers = {}
queue = Queue.Queue()
queue.put(('Erdos, P.', 0))
while not queue.empty():
(cur_author, dist) = queue.get()
if cur_author not in erdos_numbers:
erdos_numbers[cur_author] = dist
for author in adj_lst[cur_author]:
if author not in erdos_numbers:
queue.put((author, dist+1))
return erdos_numbers
def main():
num_scenario = int(raw_input())
raw_input() # Read blank line
for idx_scenario in range(1, num_scenario+1):
[num_papers, num_queries] = [int(num) for num in raw_input().split()]
adj_lst = {}
for _ in range(num_papers):
paper = raw_input()
[authors, title] = paper.split(':')
authors = [author.strip() for author in authors.split(',')]
authors = [', '.join(first_last) for first_last in zip(authors[::2], authors[1::2])]
# Build the adjacency list
for author in authors:
author_neighbors = adj_lst.get(author,set())
for coauthor in authors:
if coauthor == author:
continue
author_neighbors.add(coauthor)
adj_lst[author] = author_neighbors
erdos_numbers = calc_erdos(adj_lst)
print 'Scenario %d' % idx_scenario
for _ in range(num_queries):
author = raw_input()
print '%s %s' % (author, erdos_numbers.get(author,'infinity'))
if __name__=='__main__':
main()
输入：
1
4 3
Smith, MN, Martin, G., Erdos, P.：质因数的牛顿形式
Erdos, P., Reisig, W.：Petri 网中的口吃
Smith, MN, Chen, X.：结构化编程中的一阶导数
Jablonski, T., Hsueh, Z.：自稳定数据结构
明尼苏达州史密斯
薛，Z.
陈，X.
将输出：
方案 1
明尼苏达州史密斯 1
Hsueh, Z. 无穷大
陈 X. 2
注意：
更一般的问题可以描述为单源最短路径问题，最简单的解决方案是使用Djikstra 算法。