Exercise $3.$ Finding Paths in Search Trees

Suppose that after the call to the parent$-$finding $DFS(G,s)$ or $BFS(G,s)$ from exercise $3,$ the parent labels are stored with the nodes of the graph, and are available to you. Meaning that for any node $v,$ parent$($v$)$ will return its parent in the search tree rooted at s $,$ or NULL if there is none.

a$)$ Show the algorithm findPath $(G,v)$ which returns the path from s to v for any node v in G as a list of nodes, or NULL if there is none. Make it as simple as possible. It should be $O(k),$ where k is the number of nodes in the path.

b$)$ Given any two paths $p_x=(s,x)$ and $r_y=(s,y)$ in the search tree of G $,$ they will start with the same sequence of nodes $($in the least case, they will both start with s $).$ Note that if we reverse $p_x$ and append $p_y,$ we get a path from $x$ to $y.$

We define least common ancestor of x and y as the last node that $p_x$ and $p_y$ have in common, denoted LCA$(x,y).$

Example: $s=1,x=8,y=6,p_x=\{1,2,4,5,7,8\}$ and $p_y=\{1,2,4,6\},$LCA$(x,y)=4$

Explain how to use LCA information to give us a simple path from u to v $.$ Note that finding LCA is also a variation of Merge, like the ones we saw in the last homework.

c$)$ Based on your explanation in $($b$),$ show pseudocode to find simple paths between any two nodes in a graph, findSimplePath $(G,u,v).$ It would make calls to findPath$(G,u),$ findPath $(G,v),$ and LCA$($pathl$,$ path$2).$

d$)$ Number the lines in your pseudocode, and analyze the time complexity of your algorithm referring to the line numbers. What is the running time?