Here is how to do it. First, here is a randomly generated graph.
numnodes <- 50
the.graph <- grg.game(numnodes, 0.3)
V(the.graph)$visited <- 0
graph.degree <- degree(the.graph)
Now, we take the maximum vertex and a random vertex. (You didn't specify how you chose the second one). We randomly repick the vertex until it is connected to and is not the maximum degree vertex.
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)
}
When traversing graphs like this, I like to keep track of where I am. Here is the starting position and a line to mark these initial nodes as visited.
curpos <- c(maxvertex, randvertex)
for(num in curpos) V(the.graph)[num]$visited <- 1
Now we actually do the search and mark nodes as visited. The loop will terminate if all of the nodes are marked as visited or if there are no more connected nodes to explore. If the code is bugged, we know there shouldn't be more iterations than steps for the search, so we know if it goes over the graph is not connected and we needn't continue. For each iteration, we go through the vector containing our currently occupied nodes. If any of its neighbors haven't been visited, we mark them as visited and add them to the vector for next time. Once we have visited all of the nodes for this iteration, we start the next cycle.
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
}
Now we have visited all nodes connected to the maximal degree node. We now print the number of iterations it took to traverse the graph. If any nodes are not visited, this will additionally print a message stating that the graph is not connected.
print(curloop)
if(sum(V(the.graph)$visited) < numnodes) print("Not a connected graph.")