r - 在 R 中的广度优先搜索期间更改节点的属性

Question

我创建了一个具有 100 个节点的随机 (Erdos-Renyi) 图。我将所有100个节点的属性值设置为0。我找到度最大的节点(最多邻居)，并将其属性值从0更改为1。然后，以该节点为根节点，另一个节点作为第二个根节点，我在网络上进行广度优先搜索 (BFS)。

这与此有关question .

我这样进行广度优先搜索:

# 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(包括原来的)。

注意:两个根节点以某种方式连接(即它们之间有路径)。

抱歉这些图像，但这是基本的想法。希望这是有道理的。

任何帮助将不胜感激。谢谢!

Answer 1

这是如何做到的。首先，这是一个随机生成的图。

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.")