BFS II

Work in Progress

Summary

BFS lemmas

PropertyWhen to use it
distance[v] = distance[parent[v]] + 1Proving 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 cycleBipartiteness 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
12534678
12345678