找到兩個網頁

之間的最短路徑，我需要找到兩個維基百科頁面之間的最短距離（在「跳」）找到兩個網頁

我有一個方法來提取所有頁面

我知道的內部wiki鏈接起始目的地和結束目的地，但是我對如何從數據中提取跳躍空白很有用

到目前爲止我一直使用鏈接提取方法來填充字典，其中關鍵字是頁面上的鏈接，該值就是它被從中取走的頁面。

如果任何人有任何的想法一個什麼好數據結構，將持有的信息以及如何通過它看我會非常感激

來源

2009-12-14 Crash893

你知道graph theory什麼？您有必要的數據來構建圖表，但您需要使用Dijkstra's algorithm來遍歷它以找到兩點之間的最短路徑。

來源

2009-12-14 17:08:02

是的。或者在這種情況下，首先搜索一個簡單的寬度，因爲所有的邊都有1次點擊的權重。 – captncraig 2009-12-14 17:16:02

@CaptnCraig - 是的，我認爲你是對的。我試圖記住我所有的圖形算法，我發現Dijkstra的，所以我停止了看;） – 2009-12-14 17:19:19

也許這有點愚蠢，因爲我不是一個真正的C＃程序員，而是一個包含所有內部鏈接的多維數組，這取決於維度的深度，讓您知道哪種方式包含更少的箍環。

這只是一個想法，雖然這在理論上當然是可行的，因爲數組的維數沒有語言限制，我敢肯定它會真的記憶飢餓！

事情是這樣的：

[source] -> [source link] -> ['source link' link] -> etc 
     -> [source link] -> ['source link' link] -> etc 
     -> [source link] -> ['source link' link] -> etc 
     -> [source link] -> ['source link' link] -> [target] 
     -> [source link] -> ['source link' link] -> etc

來源

2009-12-14 17:12:15 johnnyArt

假設你有一個IEnumerable<Link> PageLinks(Link link)

跳數將由以下來解決：

Link curentPage = "somepage"; 
Link destinationPage = "otherpage"; 
if (currentPage == destinationPage) return 0; 
int hops = 1; 
IEnumerable<Link> currentLinks = PageLinks(currentPage); 
IEnumerable<Link> visited = new [] {currentPage}; 
while(!currentLinks.Contains(destinationPage)) 
{ 
    currentLinks = currentLinks 
     .SelectMany(l => PageLinks(l).Where(f => !visited.Contains(f))); 
    visited = visited.Union(currentLinks); 
    hops++; 
} 
return hops;

編輯來讓騎自行車速度更快，雖然該算法本來就沒有它。它可能會運行，直到StackOverflow或如果頁面沒有鏈接。

來源

2009-12-14 17:17:43

非常好。我喜歡使用IEnumerables來包含內存，同時循環遍歷呈指數級增長的數據集。但是，在問題中的* cyclic *圖的情況下，你不需要循環檢測嗎？如果目標從未找到，您也需要終止條件。 – 2009-12-14 17:37:54

我覺得在這種情況下圖很稀疏。因此，爲每個維基百科頁面使用HashSet之類的東西可能是一個好主意，它可以鏈接到集合內部的頁面。

在這種情況下，您並不需要實施Dijikstra的最短路徑算法。因爲這等於每條邊的權重等於1的最短路徑問題。您可以執行Breadth-first search並獲取目標頁面的深度。

來源

2009-12-14 17:18:35 Gant

是的，CaptnCraig已經發表了這個評論 - 寬度優先也會很好。 – 2009-12-14 17:24:44

下面是python中Dijkstra算法的實現：http://code.activestate.com/recipes/119466/

來源

2009-12-14 17:24:26 adamse

找到兩個網頁

回答

相關問題