$($a$)$ In what order are nodes marked as explored by BFS$?$

$($b$)$ In what order are nodes marked as explored by DFS$?$

$($c$)$ Replace the queue with a stack in BFS$,$ but do not change when nodes are explored as in DFS$.$ In

what order does this new search $($Algorithm $1)$ mark nodes as explored?

Algorithm $1$ Problem $3$

: function ModifiedBFS $(G=(V,E),s)$

mark $s$ as explored, all other nodes as unexplored

let $S$ be a stack, initialized with $s$

while $S$ is not empty do

pop node $v$ from $S$

for each neighbor $w$ of $v$ do

if $w$ is unexplored then

mark $w$ as explored

push $w$ onto $S$

An undirected graph $G=(V,E)$ is bipartite if its vertices $V$ can be colored red and blue so that

every edge has one red and one blue endpoint. Assume that $G$ is stored as an adjacency list. Describe

an $O(m+n)$ algorithm to determine whether a given graph $G$ is bipartite. Must include algorithm

description $($written out or pseudocode$),$ proof of correctness, and analysis of running time

for full credit