邻接矩阵的BFS

Question

我正在尝试在无向未加权图的邻接矩阵上实现BFS,该矩阵返回所访问的节点数.到目前为止,我已经想出了这个,但我认为这是不对的,因为当我打印出top/visited节点时,我会多次出现一些节点,而且它没有排序.我已经读过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在弹出队列后将 node设置为 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++;
        }
    }
}

Answer 2

有几个问题可以帮助我们完善答案。但是，请分享有关您返回的计数的更多详细信息。以下是需要注意的事项：

• 为什么要在 for 循环中增加计数？您可能多次对一个节点进行计数。
• Visited的大小不足以容纳所有节点。在 中std::vector<bool> visited(matrix.size(), false);，matrix.size() 仅返回外部向量的大小。这意味着Visited中最多可用一行数据。
• 用于Visited的数据结构有问题。您可以使用向量> 或在一个序列中具有 n*n 个元素的线性化向量。如果您最终使用简单的向量，则当您在Visited中查找索引时，需要将 [i][j] 索引映射到某个位置。这是一个主要问题，您无法正确跟踪节点。
• BFS 不保证排序顺序。请构造一个简单的反例来说服自己。拓扑排序可以使用BFS（或DFS）来执行。