寻找维基百科文章之间的shotest路径

我正在写一个python网络爬行程序来找到维基百科文章之间的路径。寻找维基百科文章之间的shotest路径

我有一篇开始文章和一篇目标文章，我正试图找到它们之间的短路径。

现在我基本上只是从一开始就用这样的代码进行广度搜索。

for link in to_crawl: 
    links = get_all_links(source(link), crawled) 
    if goal in links: 
     return path+[link]+[goal] 
    crawled.append(link) 
    to_crawl.append(links)

它是从一文获得到另一个，如果他们是只有几度了，但我需要一种方法来跟踪我把路径。

来源

2014-11-05 David Greydanus

下载[数据库副本]（http://en.wikipedia.org/wiki/Wikipedia:Database_download）而不是锤击Web服务器 – 2014-11-05 21:33:48

所以只要跟踪它。而不是有一个链接列表，有一个link, path对的列表。事情是这样的：

to_crawl = [(start_page, [])] 
for link, path in to_crawl: 
    links = get_all_links(source(link), crawled) 
    if goal in links: 
     return path+[link]+[goal] 
    crawled.append(link) 
    to_crawl.extend((new_link, path + [new_link]) for new_link in links)

另外请注意，你必须与你的现有代码的一个严重问题：to_crawl.append(links)附加的链接列表，就好像它是一个单一的链接，当明明你想单独追加在列表中的每个环节。我通过使用extend修复了这个问题。

作为一个便笺，path+[link]+[goal]是一个奇怪的事情要返回。例如，如果您通过路径A-B-C-D从页面A转到页面D，那么您将以B，C，D，C，D作为您的返回值，这至少可以说是很奇怪。如果您需要与路径分开的最后一个链接和目标，为什么不只是将return path, link, goal包装到路径中？

来源

2014-11-05 21:25:13 abarnert

寻找维基百科文章之间的shotest路径

回答

相关问题