All lessonsOpen Open Open Open Open
10. Graphs
BFS traversal
0 of 5 activities0%
Reading 1
Level order on graphs
BFS from a source uses a queue and a visited array.
First time you reach a node is a shortest path in unweighted graphs.
Template: push start, mark visited, while queue: pop, push unvisited neighbors.
queue<int> q; q.push(s); vis[s]=true;
while(!q.empty()){
int u=q.front(); q.pop();
for(int v: g[u]) if(!vis[v]){ vis[v]=true; q.push(v); }
}Check 2
Unweighted shortest
BFS finds shortest paths when edges are
Fill in 3
Structure
Try it 4
BFS order
Line graph 0-1-2.
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Distance in a line
Read n (nodes 0..n-1 connected i—i+1). Read s t. Print |s-t| (BFS distance on a path).
main.cpp
Loading editor…