查找两个网页之间的最短路径

Question

我需要找到两个维基百科页面之间的最短距离(在“跃点”中)

我有一种方法可以提取页面上的所有内部wiki链接

我知道起始目的地和结束目的地，但我对如何从数据中提取跃点一无所知

到目前为止，我一直在使用链接提取方法来填充一个字典，关键字是页面上的链接，值是它所在的页面。

如果任何人有任何想法，一个好的数据结构来保存信息，然后如何查看它，我将非常感激

Answer 1

你知道graph theory的事吗？您拥有构建图形所需的数据，但是需要使用Dijkstra's algorithm遍历图形以找到两点之间的最短路径。

Answer 2

也许这有点愚蠢，因为我不是一个真正的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

Answer 3

假设你有一个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。