Topological sort algorithm for Directed Acyclic Graph (DAG) is a linear arrangement of vertices such that for every directed edge x-y, vertex x comes before y in the arrangement. Topological sorting is only applicable on graphs that are DAG. Now your task is to prove that from the above graph that, "There can exist more than one topological sorting for a given graph." Using i. DFS ii. Kahn's Algorithm

Consider the following adjacent list for directed graph. adj(y)= [x], adj(x) = [z], adj(z) = [y,w], adj(w)= [x], adj(s) = [z,w], adj(v) = [s,w], adj(t)=(u,v), adj(u) = [v]. i. Draw a graph from the above information. ii. Rewrite the procedure DFS, using a stack to eliminate recursion. iii. Identify the tree edge, back edge, cross edge and forward edge for the graph.

Write down the advantage of IDS over BFS and DFS. Also, shows times and space complexity among them.