我的问题如下:考虑一个具有 10000 个节点和 4800 条边的无向图。给定这个图和给定这个图的一个节点(例如节点 1),我需要 igraph (R) 中的一个命令来获取这个节点 1 和图中最远节点之间的距离。非常感谢你的帮助!:)
亲切的问候,伊格纳西奥。
这本质上是一个探路者/搜索。
假设 isConnected(a,b) 返回两个节点是否连接
(我是用 Lua 写代码,应该不难翻译)
function search(list)
local i = 0
while i < 10000 do
i = i + 1
if isConnected(i,list[#list]) then
--This expression refers to the last member
search(list ++ i)
--Although not technically a proper operator, ++ adds the element to the end of the list
end
end
submit_list(list)
end
submit_list
是一个接受列表并检查它们的函数。它找到最长的不包含重复项的提交列表。该列表将解决您的问题。
哦,另一件事;我的代码没有说明什么。如果列表包含重复节点,则该函数应终止,以便它不会永远递归。
> g <- erdos.renyi.game(100,1/20)
> s <- c(shortest.paths(g,2))
> s
[1] 3 2 0 3 3 3 3 3 3 3 3 3 3 2 1 2 3 1 3 3 3 4 2 4 3 2 3 2 2 3 3 2 3 2 4 4 3
[38] 3 3 2 2 3 3 4 2 3 3 2 2 4 3 2 3 3 2 1 2 4 2 2 2 2 1 2 4 3 2 2 2 4 3 4 3 3
[75] 3 3 3 3 3 2 1 3 2 4 2 1 3 1 3 3 3 3 4 3 2 3 2 2 3 3
> which(s == max(s))
[1] 22 24 35 36 44 50 58 65 70 72 84 93
> get.shortest.paths(g,2,21)
[[1]]
[1] 2 55 33 50 21
让我们做一个图表
g <- erdos.renyi.game(100,1/20)
这将找到到顶点 2 的距离
s <- c(shortest.paths(g,2))
查找最远顶点的索引
which(s == max(s))
显示路径
get.shortest.paths(g,2,21)