CODEWITHSUNDEEP
c++breadth-first-search
TJain
TJain

Reputation: 466

BFS on Adjacency Matrix

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

Upvotes: 9

Views: 12728

Answers (2)

Jonathan Darryl
Jonathan Darryl

Reputation: 946

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

Upvotes: 5

KalyanS
KalyanS

Reputation: 527

There a few questions, to help us hone the answer. But, please share more details on the count that you get back. Here are the things to look at:

  • Why do you increment the count inside the for loop? You are possibly counting a node multiple times.
  • The size of Visited isn't sufficient to hold all the nodes. In std::vector<bool> visited(matrix.size(), false);, matrix.size() returns only the outer vector's size. It means that at most one row worth of data is available in Visited.
  • The data structure used for Visited is problematic. Either you use a vector> or a linearized vector that has n*n elements in one sequence. If you end up using a simple vector, you need to map a [i][j] index into a position when you look up the index in Visited. This is a major issue and you cannot track the nodes correctly.
  • Sorted order is not guaranteed out of a BFS. Please construct a simple counter example to convince yourself. Topological Sort can be performed using BFS(or DFS).

Upvotes: 0

Related Questions