Breadth First Search (BFS)
Algorithm
Breadth-first search, or BFS, is an algorithm for searching through a graph in a systemic "breadth first" order. BFS is an important fundamental graph
Run Time
$$\mathcal{O}(|V| + |E|)$$
Space
$$\mathcal{O}(|V|)$$
The Algorithm
Breadth-first search traverses a graph $G(V, E)$, with vertices $v \in V$ and edges $(v, w) \in E$, starting from a given vertex $s$ and visits vertices in order of increasing distance from $s$.
To do so, we utilize a queue and an array to keep track of vertices we have already visited. We begin the BFS by pushing $s$ to the queue and setting it to "visited". Then, we pop a vertex $v$ from the front of the queue and push all unvisited vertices reachable from $v$ to the back of the queue. We repeat this until the queue is empty (i.e. all vertices reachable from $s$ have been visited).
Pseudocode
def BFS(vertices V, edges E, starting_vertex s):
# Initialize an array to track visited vertices, set s to visited
visited = len(V) * list(False)
visited[s] = True
# Initialize a queue to track what vertices to visit next, push s to the queue
Q = queue()
Q.push(s)
# Pop a vertex from the queue, call it v
# Push all unvisited vertices reachable from v to the queue
# Repeat until the queue is empty
while len(Q) != 0:
v = Q.pop()
for (v, w) in E:
if not visited[w]:
visited[w] = True
Q.push(w) Resource Analysis
Time Complexity
Each vertex can be pushed and popped from the queue at most once. Since there are $|V|$ vertices and each operation takes $\mathcal{O}(1)$ time, the total time due to queue operations is $\mathcal{O}(|V|)$ time.
For each vertex, $v$, we need to search through the edge set, $E$, for all edges from $v$ to some other vertex $w$, $(v, w) \in E$. How long this takes depends on the specific representation of the graph. In the adjacency list representation, finding each neighboring vertex takes $\mathcal{O}(1)$ time, and each edge is only searched for once. Thus, since there are $|E|$ edges, the total time for edge-finding operations is $\mathcal{O}(|E|)$. Therefore, the overall runtime (using the adjacency list representation) is $\mathcal{O}(|V| + |E|)$. Note that $|E|$ can range from $\mathcal{O}(1)$ to $\mathcal{O}(|V|^2)$, depending on how sparse the graph is.
Sapce Complexity
The queue contains at most $|V|$ elements at any given time, so assuming that we can represent each vertex in $\mathcal{O}(1)$ space, the queue requires a total of $\mathcal{O}(|V|)$ space. Likewise, the visited array contains one element per vertex, for a total of $\mathcal{O}(|V|)$ space. Therefore, the overall space required is $\mathcal{O}(|V|)$