BFS II
Summary
BFS lemmas
| Property | When to use it |
|---|---|
distance[v] = distance[parent[v]] + 1 | Proving parent paths have the recorded length |
| For an undirected edge ({u,v}), ( | d[u]-d[v] |
| For a directed edge (u -> v) with reachable (u), (d[v] <= d[u]+1) | Shortest-path inequalities |
| BFS reaches exactly the vertices reachable from (s) | Reachability and connected components |
| In an undirected graph, an edge within one BFS layer implies an odd cycle | Bipartiteness proofs |
Concept
At the end visited[v]=true iff there is a path from s to v in G
BFS for shortest path
-
in an unwighted/uniform weight graph
-
no other shorter path
-
the distance to elements added to the queue is non decreasing as more vertices are added
Connected components
Components(G):
for each vertex v in G:
comp[v] = 0
c = 0
for each vertex s in G:
if comp[s] == 0:
c = c + 1
comp[s] = c // vertex s is in component number c
visited = Reachable(G,s)
for each vertex v in visited:
comp[v] = c // assign all reachable verticies to component number c
return (comp, c)
Time complexity
Bipartite graph
- odd length cycles?
- redraw the BFS tree in a BST form
BFS tree
- cannot have non-tree edges cross multiple levels