查找网络节点之间的路径距离？

我正在写一个网络爬虫，我需要找到两个网址之间的最小距离。查找网络节点之间的路径距离？

我用hash表示网络。每个节点，这是不在网的末端，键接到节点的向量，其所连接的：

hash = {:v0 => [:v1, :v2, :v3], 
     :v1 => [:v4, :v5, :v6], 
     :v2 => [:v7, :v8, :v9], 
     :v3 => [:v10, :v11, :v12], 
     :v4 => [:v13, :v14, :v15]}

该溶液不工作。问题是，我只递增的距离（距离变量），当它发现目标，所以结果总是1：

def path src, target, hash, dist 
    return -1 if hash[src] == nil # invalid distance if source is invalid 
    return dist += 1 if hash[src].include? target 

    arr = Array.new 
    for i in hash[src] do 
     arr.push path(i, target, hash, dist) 
    end 
    arr = arr.delete_if {|x| x < 0} # delete invalid values 
    return -1 if arr.empty? 
    return arr.min # return the shortest distance 
end

如何解决它，所以它会在网的每一层上增加？

来源

2013-02-11 mzdravkov

我修好了。这里是代码，如果它有助于某人。

def distance src, target, hash 
    return 0 if src == target 
    return nil if hash[src].nil? 
    dist = 1 

    if hash[src].include? target 
     return dist 
    else 
     arr = hash[src].map {|x| distance x, target, hash} 
    end 
    arr = arr.delete_if {|x| x.nil?} 

    return dist + arr.min if !arr.empty? 
    return nil 
end

来源

2013-02-12 10:15:27 mzdravkov

看起来你并没有完全理解递归的想法。为此，首先写下你的“路径距离”的定义。我之所以这么说，是因为我希望你想要的是距离，或者你想要的路径（路径的长度是距离），但我并不知道你需要什么。

现在，重要的原因是，在这种情况下，可能类似于“路径是从当前URL到目标URL的最短距离”。实现类似于“如果目标URL是直接邻居，则距离为1，否则它是距离任何邻居加上1的最短距离”。在你的情况下，你通过一个现有的距离，这并不是真的错，而是不寻常的。接下来，如果您在hash[src]中找到网址，那么您将增加该距离（是Ruby通过引用，BTW？）和会将其返回。在那一点上，我实际上会希望你返回1，因为那是目前位置和目标之间的距离。同样，稍后，在将它传递给递归调用之前，您可能还需要增加dist。

现在，还有一个完全不同的问题，那就是你的算法效率低下，以至于它将变得毫无用处并且只有很少的URL。我们假设这些URL是以“A - X - T”的形式连接的，其中X是开始，T是目标。如果你不走运，你首先会进入A，这可能是成千上万个URL的云。遍历整个图之后，其中的每一个都会找到T的路径。看一看广度优先搜索（BFS）和深度优先搜索（DFS）之间的区别，它会给你一个提示如何解决它。

两两件事：

考虑A和A之间的路径，我会说，他们的距离是零，你的函数应该处理。距离就变成：如果S = T，则距离为零，否则为距离任何邻居最近的距离加1。
我会尽量避免使用-1作为“未找到”。我宁愿不返回任何东西（零？），因为那样你不小心在它上面做任何算术。

来源

2013-02-12 05:28:31

查找网络节点之间的路径距离？

回答

相关问题