擅长:python、mysql、java
<p>可能是无限递归。你正在搜索一棵扎根在目标上的树;树上的一些路径到达了它们上游的点。你需要一种方法来认识到这一点,当它发生时不要再往下看了。在</p>
<p>一种方法是在路上保留祖先的名单。比如:</p>
<pre><code>def getDegrees(target, base, dos, ancestors): # Also carry a list of "ancestors"
for actor in actedWith[base]:
if target == actor:
print base, "has ", dos, " degree(s) of separation from ", target
return
dos = dos+1
ancestors = ancestors + [base] # Must be separate variable binding to avoid mutating the caller's copy
for actor in actedWith[base]:
if actor in ancestors: continue # Check if on path, skip if so
getDegrees(target, actor, dos, ancestors)
...
getDegrees(target, base, dos, [target])
</code></pre>
<p>请注意,“祖先”指的是道路上的一个点,而不是演员可能与之相关的人。在</p>
<p>这并不能避免一个actor拥有<code>actedWith</code>他们自己的情况(希望输入文件永远不会包含这些内容),但是只要稍加修改就可以了。在</p>