1. BFS for cycle detection (Exercise 11.129 on page 1161 in textbook.) Input: G (V, E) and source node, sEV Output: true if and only if s involved in cycle Frontier (sh while Frontier is nonempty do Set u equal to first node in Frontier and remove u from Frontier if s is neighbor of u then return true for every neighbor v of u do if v is not in Frontier or Known then add v to the end of Frontier add u to Known return false (a) Give an undirected graph with no cyeles, for which the algorithm incorrectly returns true (b) Explain how to fix the algorithm (c) State the loop invariant for the while loop of the new algorithm, and prove it using induction 1. BFS for cycle detection (Exercise 11.129 on page 1161 in textbook.) Input: G (V, E) and source node, sEV Output: true if and only if s involved in cycle Frontier (sh while Frontier is nonempty do Set u equal to first node in Frontier and remove u from Frontier if s is neighbor of u then return true for every neighbor v of u do if v is not in Frontier or Known then add v to the end of Frontier add u to Known return false (a) Give an undirected graph with no cyeles, for which the algorithm incorrectly returns true (b) Explain how to fix the algorithm (c) State the loop invariant for the while loop of the new algorithm, and prove it using induction