Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
1.1 kB
1
Indexable
Never
    vector<int> bfsOfGraph(int V, vector<int> adj[]) {
        queue<int> q;
        q.push(0);
        vector<int> bfsVec;
         // true for a node if its in either visited or explored state.
        bool visited[V] = {false};
        visited[0] = true; // Explored.
        
        while (!q.empty()) {
            // now here visited[node] implicitly mean its in visited state.
            int node = q.front();
            q.pop();
            bfsVec.push_back(node);
            
            for (int j = 0; j < adj[node].size(); j++) {
                int connectedNode = adj[node][j];
                if (!visited[connectedNode]) {
                    // mark as true to represent the node is in explored state
                    // and when in next level traversal it will be picked up, we
                    // can implicitly consider this true value to mean
                    // that time, that the node is in visited state.
                    visited[connectedNode] = true;
                    q.push(connectedNode);
                }
            }
        }
        
        return bfsVec;
    }