Breadth First Search (BFS)

Breadth First Search (BFS) can be used to explore nodes in different layers, compute shortest paths and connected components of undirected graph. The run time complexity is in linear time O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges in the graph. Initally all nodes are not visited, starting from vertex 1 in a graph G, mark 1 as visited. Let ``q`` be a FIFO queue, initialized with 1. While ``q`` is not empty, remove the first node of ``q`` called ``v``. For each edge ``u``, if ``u`` is not visited, mark it visited and add it to ``q.`` ```cpp memset(vis, 0, sizeof(vis)); queue<int> q; q.push(1); vis[1] = 1; while(!q.empty()) { int v = q.front(); q.pop(); for(auto u : g[v]) { if(!vis[u]) { vis[u] = 1; q.push(u); } } } ``` If vis[x] is 1, we can say that G has a path from 1 to x. Applications: - Shortest Paths ``` dist[v] = 0 if v = s, else INT_MAX for edge (v, u) if v is not visited set dist[u] = dist[v] + 1 ``` The shortets path result is stored in ``dist[u]``. - Connected Components via BFS ``` for i = 1 to n if not visited bfs(g, i) ```