Cycle Detection A cycle is a path of edges from a node to itself You are given a directed graph G = (V,E), and a special vertex u Give an algorithm based on BFS that determines in O(V+ E) time whether v is part of a cycle You are given a graph G = (V,E), and you are told that every vertex is reachable from vertex s. You want to determine whether the graph has any cycles. Ben Bitdiddle proposes the following algorithm. Perform a BFS from s If, during the search, you ever reach a node that you have already seen before, then declare that G has a cycle. If you never reach the same node twice, declare that there is no cycle i. Show that Ben's algorithm works for undirected graph:s ii. Show that Ben's algorithm does not work for directed graphs You are given a directed graph G = (V, E). Give an algorithm based on DFS that determines in O(V E) time whether there is a cycle in G Cycle Detection A cycle is a path of edges from a node to itself You are given a directed graph G = (V,E), and a special vertex u Give an algorithm based on BFS that determines in O(V+ E) time whether v is part of a cycle You are given a graph G = (V,E), and you are told that every vertex is reachable from vertex s. You want to determine whether the graph has any cycles. Ben Bitdiddle proposes the following algorithm. Perform a BFS from s If, during the search, you ever reach a node that you have already seen before, then declare that G has a cycle. If you never reach the same node twice, declare that there is no cycle i. Show that Ben's algorithm works for undirected graph:s ii. Show that Ben's algorithm does not work for directed graphs You are given a directed graph G = (V, E). Give an algorithm based on DFS that determines in O(V E) time whether there is a cycle in G