BFS从给定节点开始，到达所有节点

Question

我有一个场景

1. 我想从一个特定的节点（比如ID:7）开始运行BFS
2. 如果有无法从该节点访问的节点，我想重新启动BFS（使用任何剩余节点），直到访问图的所有顶点

到目前为止，我得到的是从节点0开始并用另一个未访问的顶点重新启动的代码（部分）：

void BFS()
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
    // Call the recursive function starting from all vertices one by one
    for(int i = 0; i < V; i++)
        if(visited[i] = = false)
            BFSUtil(i,visited);
}

void BFSUtil(int s,bool *visited)
{
    queue<int> queue;
    visited[s]=true;
    queue.push(s);

    while(!queue.empty())
    {
        s = queue.front();
        queue.pop();
         // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!visited[i])
            {                
                queue.push(i);
                BFSUtil(id,visited);
            }
        }
    }

}

如何有效地更改此代码以满足我的要求？

Answer 1

你已经准备好了大部分想法，因为你正在存储这个访问的状态，并且#1已关闭。要执行#2，只需在已访问的列表中迭代，查找值false，以指示未访问的节点。现在在那个上面运行#1。重复上述操作，直到您发现已访问的中的所有条目均为真。

比如：

// Loop until all elements have been visited.
bool found = false;
do
{
    // Look for an element that hasn't been processed yet
    // to run the BFS.
    found = false;
    for(int i = 0; i < V; i++)
    {
        if(visited[i] = = false)
        {
            BFSUtil(i,visited);    
            found = true;
        }
    }
} while (found);

你也可以避免每次在#1之后通过访问进行线性搜索，使用一个比线性搜索更有效的集合，但所需的努力可能不值得，除非你搜索的是一大堆小的、不连续的图，这通常会降低遍历的性能，除非它是一个真正有效的集合（或密集稀疏的集合：一个用于常数时间快速检查，另一个用于日志或更好的时间插入）。