我正在尝试在无向未加权图的邻接矩阵上实现 BFS,它返回访问的节点数。到目前为止,我已经想到了这个,但我认为这是不正确的,因为当我打印出顶部/访问过的节点时,我得到了一些节点的多次出现,而且它没有排序。我在某处读到 BFS 是一种拓扑排序,我得到的顺序没有排序。
int BFS(std::vector<std::vector<int> > &matrix, int start)
{
std::vector<bool> visited(matrix.size(), false);
std::queue<int> Q;
Q.push(start);
int count = 0;
while( ! Q.empty())
{
int top = Q.front(); Q.pop();
visited[top] = true; count++;
for (int i = 0; i < matrix.size(); ++i)
{
if(matrix[top][i] != 0 && (! visited[i]) )
{
Q.push(i);
}
}
}
return count;
}
最佳答案
不是在弹出队列后将visited
节点设置为true,而是在将其插入队列时设置它,并在里面添加计数,以防止某些节点重复计数。请引用以下内容:
//..previous lines
Q.push(start);
visited[start] = true;
int count = 1;
while(!Q.empty()){
int top = Q.front(); Q.pop();
for (int i = 0; i < matrix.size(); ++i){
if(matrix[top][i] != 0 && (! visited[i]) ){
Q.push(i);
visited[i] = true;
count++;
}
}
}
关于c++ - 邻接矩阵上的 BFS,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36899181/