Queues

A queue processes elements in first-in, first-out order, abbreviated FIFO: the oldest waiting item is handled next. Queue operations let us append new work at the back, inspect the next item at the front, and remove that item when finished. The same discipline makes Breadth-First Search explore an unweighted graph one distance layer at a time. This lesson develops the queue interface first, then implements multi-source BFS: finding every vertex’s shortest distance to any member of a chosen source set.

Prerequisites: Adjacency lists, loops, and Arrays and Vectors.

Build the idea

1. 1. Learn the FIFO interface. Include <queue> and declare queue<int> q;. q.push(x) inserts x at the back; q.front() reads the oldest item; q.back() reads the newest. q.pop() removes the oldest item and returns nothing. Copy front first if you need the removed value. q.empty() tests whether the queue has no items, and q.size() counts them. Always check empty before front, back, or pop. A queue intentionally has no arbitrary indexed access: its interface expresses the order in which work must be processed.
2. 2. Trace operations before applying an algorithm. Starting empty, push 8, push 3, then push 5. From front to back the contents are [8,3,5]; front is 8, back is 5, and size is 3. Pop removes 8, leaving [3,5]. Pushing 9 now produces [3,5,9], not [9,3,5]. Equal values are allowed and remain separate entries. A queue is an adaptor: by default C++ stores its elements in a deque, while hiding that container’s extra operations. These queue operations are O(1) with that default backing container. A vector with repeated erase(begin()) would shift elements and is a poor substitute.
3. 3. Explain the BFS invariant. Give each unvisited vertex distance -1. Set the start distance to zero and enqueue it. When vertex v is removed, an unvisited neighbor receives dist[v]+1 and is enqueued. The queue holds vertices in nondecreasing distance order. Every new neighbor is appended after previously discovered vertices, so no length-(d+1) candidate can jump ahead of unfinished length-d work. If there were a shorter path to that neighbor, its preceding vertex would have been processed earlier and discovered it already. This proves that the first assigned distance is shortest in an unweighted graph.
4. 4. Generalize to several sources. Instead of running BFS repeatedly, enqueue all sources before beginning. Each starts at distance zero. The first wave reaches every vertex one edge from any source, the second wave reaches distance two, and so on. The result is the minimum distance to the whole source set. For the path 1–2–3–4–5–6 with sources 1 and 5, initial queue [1,5] leads to distances [0,1,2,1,0,1]. This is equivalent to adding an artificial super-source with zero-cost links, but no extra vertex is needed in the implementation.
5. 5. Mark before insertion. The program assigns distance when a vertex enters the queue. That distance also acts as its visited flag. Marking only when removing allows several neighbors to enqueue the same vertex before its first removal. Distances might still be repairable, but the clean one-enqueue-per-vertex bound is lost. Duplicate sources are ignored for the same reason. Disconnected vertices remain -1, which is different from distance zero. Parallel edges do not affect correctness because the first visit check prevents duplicate work on vertices.
6. 6. Read the graph representation. g[v] lists neighbors of vertex v. Each undirected edge is stored twice. dist[v] is both reachability information and the shortest distance to any source. The queue stores only vertex IDs because each current distance is already in dist; storing a second copy is unnecessary here. The sample deliberately includes an isolated vertex. A source with no neighbors is still reachable from itself at distance zero, while an isolated non-source stays unreachable. An empty source set leaves every distance -1.
7. 7. Know the shortest-path boundary. FIFO ordering is the source of the proof, not a cosmetic implementation choice. Replacing the queue by a stack changes the exploration order and generally loses the shortest-path guarantee. Likewise, when edge costs differ, reaching a vertex through fewer edges may cost more. Use a deque-based 0–1 BFS when every edge weight is zero or one, or a min-priority queue with Dijkstra for general nonnegative weights. Ordinary BFS requires equal edge costs. Directed BFS uses only outgoing adjacency entries; the runnable example adds both directions because its graph is undirected.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    if(!(cin>>n>>m>>k)||n<1||m<0||k<0){
        return 0;
    }
    vector<vector<int>>g(n+1);
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        if(u<1||u>n||v<1||v>n){
            return 0;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // -1 also marks an undiscovered vertex; every initial source has distance 0.
    vector<int>dist(n+1,-1);
    queue<int>q;
    for(int i=0;i<k;++i){
        int s;
        cin>>s;
        if(s<1||s>n){
            return 0;
        }
        if(dist[s]==-1){ // Ignore a repeated source.
            dist[s]=0;
            q.push(s);
        }
    }
    while(!q.empty()){
        // FIFO order processes distance layers before later layers.
        int v=q.front();
        q.pop();
        for(int next:g[v]){
            if(dist[next]!=-1){
                continue;
            }
            dist[next]=dist[v]+1; // Mark before enqueuing.
            q.push(next);
        }
    }
    for(int v=1;v<=n;++v){
        if(v>1){
            cout<<' ';
        }
        cout<<dist[v];
    }
    cout<<'\n';
}

Complexity analysis

With std::queue’s default deque backing store, push, pop, front, back, empty, and size are O(1). BFS initializes n distances, processes each reachable vertex once, scans at most 2m stored adjacency entries, and reads k sources: O(n+m+k) total time. Graph storage is O(n+m); the distances and waiting queue use O(n) extra space. Duplicate source IDs are ignored, so they do not enlarge the queue beyond n entries. There is no sorting or per-query preprocessing hidden in the BFS loop.

Example input and output

Read n m k, then m undirected edges u v, then k source IDs. Vertices are 1..n, edges have unit weight, and k may be zero. Print n shortest distances to the source set, using -1 when unreachable.

Input

7 5 2
1 2
2 3
3 4
4 5
5 6
1 5

Output

0 1 2 1 0 1 -1

Each value is distance to source 1 or 5, whichever is nearer. Vertex 3 is two edges from either. Vertex 7 has no path to a source and is printed as -1.

Practical applications

Use queues for unweighted shortest paths, nearest-source distances, level-order tree traversal, propagation simulations, and Kahn’s topological sort. Queue order also models first-arrival task processing. A deque is the related structure for changes at either end; a priority queue selects by priority rather than arrival time. The separate Deques lesson develops both-end operations without changing the FIFO contract taught here.

Check your understanding

After pushing 8, then 3, then 5 into an empty queue and popping once, what are front and back?

Put it into practice

Also print one nearest source ID for every reachable vertex.