尋找維基百科文章之間的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路徑

回答

相關問題