1 Induction on queue

• n is the starting node of the bfs
• edgelist is the neighbor nodes of n

void bfs(int n, vector<vector<int>>& edgelist, vector<int>& dist, queue<int>& q) {
    
    for (int i : edgelist[n]) {
        if (dist[i] != -1) continue;
        dist[i] = dist[n] + 1;
        q.push(i);
    }
# invariant: top of queue is an immediate neighbor node of n
    if (!q.empty()) {
        n = q.front();
        q.pop();
        bfs(n, edgelist, dist, q);
    }
}

The topological ordering on the neighbors of n aka head of queue is the induction variable.

Front of Queue                                          End of Queue
n | neigh1_A | neigh1_B | neigh1_C | ... | neigh4_A | neigh4_B | ...

2 Examples

• PROBLEM: A set of N nodes of a COMPLETE graph with 1 way edges connecting them. Show there exist a path that reaches every node.
• SOLUTION:
  • Pick X to be some arbitrary node.
  • Partition K nodes to 2 set of disjoint nodes K and L
    • let K nodes to be the complete path from an arbitrary origin Y that ENDS at X.
    • let L nodes to be the complete path from an arbitrary origin Y that STARTS at X.
  • K and L are disjoint sets of nodes
  • IH is what allows us to build paths K and L