我需要找到两个维基百科页面之间的最短距离(以“跃点”为单位)
我有一种方法可以提取页面上的所有内部 wiki 链接
我知道起点和终点,但我对如何从数据中提取跃点一无所知
到目前为止,我一直在使用链接提取方法来填充字典,其中键是页面上的链接,值是它被取消的页面。
如果有人有任何想法,那么一个好的数据结构将是保存信息然后如何查看它,我将非常感激
我需要找到两个维基百科页面之间的最短距离(以“跃点”为单位)
我有一种方法可以提取页面上的所有内部 wiki 链接
我知道起点和终点,但我对如何从数据中提取跃点一无所知
到目前为止,我一直在使用链接提取方法来填充字典,其中键是页面上的链接,值是它被取消的页面。
如果有人有任何想法,那么一个好的数据结构将是保存信息然后如何查看它,我将非常感激
你知道图论吗?您拥有构建图形所需的数据,但您需要使用Dijkstra 算法来遍历它以找到两点之间的最短路径。
也许这有点愚蠢,因为我不是真正的 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
这是 Dijkstra 算法在 python 中的实现:http: //code.activestate.com/recipes/119466/
假设你有一个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 左右。
我认为在这种情况下图表是稀疏的。因此,为每个 Wikipedia 页面使用类似 HashSet 之类的东西可能是一个好主意,它链接到集合内的页面。
在这种情况下,您实际上不需要实现 Dijikstra 的最短路径算法。因为这等于每条边的权重等于 1 的最短路径问题。您可以进行广度优先搜索并获取找到目标页面的深度。