Notes - DAA HT23, Breadth-first search

Created: May 23, 2023

What type of data structure is used when implementing breadth-first search?

A FIFO queue.

Running breadth-first search gives rise to a “breadth-first search tree”, a graph $G = (V _ \pi, E _ \pi)$. How is $E _ \pi$ defined?
\[E_\pi = \\{(\pi[u], u): u \in V_\pi\\}\]

What is the running time of breadth-first search?
\[O(|V| + |E|)\]

Can you state pseudocode for breadth-first search on a graph $G$ and from a start vertex $s$?

 
BFS(G, s):
	for each vertex u in G\{s}:
		u.color = white
		u.d = infinity
		u.pi = null
	
	s.color = grey
	s.d = 0
	s.pi = null

	ENQUEUE(s)
	
	while queue is not empty:
		u = DEQUEUE()
		for each vertex v adjacent to u:
			if v.color == white:
				v.color = grey
				v.d = u.d + 1
				v.pi = u
				ENQUEUE(v)
				
		u.color = black


Related posts