c++ - 邻接矩阵上的 BFS

Question

我正在尝试在无向未加权图的邻接矩阵上实现 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;
}

Answer 1

不是在弹出队列后将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++;
        }
    }
}