擅长:python、mysql、java
<p>虽然@newbie的观点是“您只需要检查路径的所有边是否有效”是正确的,但是他给出的实现远没有效率;<code>graph.edges()</code>为路径中的每一条边从头开始重建一个图的所有边的列表。应该始终使用<code>(u, v) in g.edges()</code>,而不是<code>(u, v) in g.edges()</code>,这是一个常量时间操作。尽管目前看来您正在使用<code>DiGraph</code>,但后一种方法还有一个额外的好处,即既能为<code>Graph</code>和{<cd4>}工作,而前面的方法只适用于<code>DiGraph</code>。(这是因为<code>Graph</code>的<code>edges()</code>方法只返回一个(随机)方向的边,因此只检查一个方向的边是不够的;<code>g.has_edge()</code>对<code>Graph</code>和<code>DiGraph</code>都是正确的)</p>
<p>长话短说,使用:</p>
<pre><code>def accepts(g, path):
return all([g.has_edge(path[i], path[i+1]) for i in range(len(path)-1)])
</code></pre>
<p>或者更简洁一点:</p>
^{pr2}$