BFS on Adjacency Matrix

Question

I'm trying to implement a BFS on adjacency matrix of undirected unweighted graph which returns the number of nodes visited. I've come up with this till now but I think this is not right as when I print out the top/ visited node, I'm getting multiple occurrences of some nodes as well as it's not sorted. I've read somewhere that BFS is a topological sort and the order I get is not sorted.

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;
}

Solution

Instead of setting visited node to true after popping the queue, you should set it when you insert it to the queue, and add count inside as well, as to prevent double counting of some nodes. Please refer to the following:

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

Comments

[TJain]

That count was left by mistake as I forgot to remove it after trying different variations. I've edited and removed it now. I believe, the visited array can hold all nodes as the adjacency matrix will be n*n if the graph has n nodes. Hence, visited can take care of all nodes. Ok, it may not perform a sort always, but it is not supposed to visit the same node multiple times. I added a print statement for top after visited[top] = true and found repetition of nodes which I think does not happen in BFS.

[KalyanS]

You are missing one key point: in the declaration of visited, you specify the size as matrix.size(). But, matrix is a vector of vector. When you say matrix, size(), you get the outer vector's size. But, visited may potentially need to have all the elements.

[TJain]

I arrived at the answer as well by hit and trial, but fundamentally the for loop is for adding all the neighbours of the visited node, right ? And isn't it the same if we visit it when we're removing from the Queue or should I just add (not in Queue) when doing the if ?

[Jonathan Darryl]

no, it's not the same. example: say u have (1)->(2), (3) and (2)->(3). If you count++ when you pop the queue, the (3) node is counted twice.

[TJain]

But the number of elements = size of outer matrix as it's an adjacency matrix.