邻接矩阵上的BFS

Question

我试图实现一个无向未加权图的邻接矩阵上的BFS，它返回访问的节点数。到目前为止，我已经提出了这个，但我认为这是不对的，因为当我打印出top/vised节点时，我得到了一些节点的多次出现，而且它没有排序。我在某个地方读到过，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;
}

Answer 1

不是在弹出队列后将visited节点设置为true，而是在将其插入队列时将其设置为true，并在队列中添加count，以防止某些节点的重复计数。请参阅以下内容：

//..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++;
        }
    }
}