我创建了一个具有100个节点的随机（Erdos-Renyi）图。我已将所有100个节点的属性值设置为0。我找到了度数最大（邻居最多）的节点，并将其属性值从0更改为1。然后，将该节点用作根节点，并使用另一个节点作为第二个根节点，我在网络上进行了广度优先搜索（BFS）。
这与这个问题有关。
我像这样进行广度优先搜索：
# BFS on the network
bfs <- graph.bfs(graph, root = c(root_node, root_node2), unreachable = FALSE,
order = TRUE, dist = TRUE)
我要查看第一个根节点的邻居，然后是第二个根节点的邻居，然后是第一个根节点的邻居的邻居，然后是第二个根节点的邻居的邻居，依此类推。
所以像这样：
O # Note: O* is the first root node
| # and O! is the second root node
|
O----O----O!----O----O*----O----O----O
| |
| |
O O
因此，首先查看第一个根节点的邻居：
O # Note: double connections are
| # the paths taken to the neighbors
|
O----O----O!----O====O*====O----O----O
| ||
| ||
O O
然后查看第二个根节点的邻居：
O
|
|
O----O====O!====O----O*----O----O----O
|| |
|| |
O O
然后，第一个根节点的邻居的邻居：
O
||
||
O----O----O!----O----O*----O====O----O
| |
| |
O O
然后是第二个根节点的邻居的邻居：
O
|
|
O====O----O!----O----O*----O----O----O
| |
| |
O O
依此类推，直到检查完所有节点为止：
O
|
|
O----O----O!----O----O*----O----O====O
| |
| |
O O
在查看每个节点时，我想将其属性值从0更改为1，这样，如果有另一个路径到达，它便知道该节点已被查看。
另外，是否有一种方法可以计算遍历所有节点的迭代次数？例如，这里是6（包括原始的）。
注意：两个根节点以某种方式连接（即，它们之间有一条路径）。
对不起图像，但这是基本概念。希望这是有道理的。
任何帮助将非常感激。谢谢！
这是怎么做。首先，这是一个随机生成的图。
numnodes <- 50
the.graph <- grg.game(numnodes, 0.3)
V(the.graph)$visited <- 0
graph.degree <- degree(the.graph)
现在，我们采用最大顶点和随机顶点。（您没有指定如何选择第二个）。我们随机重新选择顶点，直到该顶点连接到最大度数顶点为止，而不是最大度数顶点。
maxvertex <- sample(which(graph.degree == max(graph.degree)),1)
randvertex <- as.integer(sample(V(the.graph),1))
while((randvertex == maxvertex) ||
(shortest.paths(the.graph,maxvertex,randvertex) == Inf)) {
randvertex <- sample(V(the.graph),1)
}
当遍历这样的图形时，我喜欢跟踪自己的位置。这是起始位置和一行，将这些初始节点标记为已访问。
curpos <- c(maxvertex, randvertex)
for(num in curpos) V(the.graph)[num]$visited <- 1
现在，我们实际上进行搜索并将节点标记为已访问。如果所有节点都标记为已访问，或者没有更多连接的节点可供探索，则循环将终止。如果代码有错误，我们知道搜索的迭代次数不应超过搜索的步骤，因此我们知道它是否遍历了图未连接并且不需要继续。对于每次迭代，我们都要遍历包含当前占用节点的向量。如果尚未访问过它的任何邻居，我们会将其标记为已访问并将其添加到向量中，以备下次使用。一旦访问了此迭代的所有节点，便开始下一个循环。
maxloops = length(V(the.graph))
curloop = 0
while((curloop < maxloops) && (length(curpos)>0) &&
(sum(V(the.graph)$visited) < numnodes)) {
nextpos <- c()
while(length(curpos)>0) {
curnode <- curpos[1]
curpos <- curpos[-1]
adjnodes <- which(the.graph[curnode] == 1)
for(adjnode in adjnodes) {
if(!V(the.graph)[adjnode]$visited) {
nextpos <- c(nextpos,adjnode)
V(the.graph)[adjnode]$visited <- 1
}
}
}
curpos <- nextpos
curloop <- curloop + 1
}
现在，我们已经访问了连接到最大度节点的所有节点。现在，我们打印遍历图形所需的迭代次数。如果未访问任何节点，这将另外打印一条消息，指出该图未连接。
print(curloop)
if(sum(V(the.graph)$visited) < numnodes) print("Not a connected graph.")
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句