Please help with deapth first search algorithm producing wrong input$[25]$: # Given an adjacency list a$,(15$ points$)$ Implement Breadth First and Depth First Search

Given an adjacency list a$,$

bfs $(a,u)$ performs a breadth first search starting at node $u$ and returns a list of nodes in the order in which they were seen.

INPUT: $[[1].[2],[0]],1($a $3$ node cycle, starting BFS at node $1)$

OUTPUT: $1,2,0$

dfs$($a$)$ performs a depth first search starting at node $0$ and returns a list of nodes in the order in which they were seen, with start and stop times.

INPUT: $[[1],[2],[0]]($a $3$ node cycle$)$

OUTPUT: $[(0,(1,6)),(1,(2,5)),(2,(3,4))]$

Note: Choose the next node in numerical order $($node $3$ is searched before node $5).$ The adjacency lists are already sorted in this order.

You may use the heapq library for queues.

Be careful of the formatting for DFS$.$ Each element of the return list is a tuple containing an int and another tuple: $($node$\_$id$,($start$\_$time, stop$\_$time$))$

$$

#dfs$($a$)$ performs a depth first search starting at node $0$ and returns a list of nodes in the order in which they were seen, with start and stop times.

#INPUT: $[[1],[2],[0]]($a $3$ node cycle$)$

#OUTPUT: $[(0,(1,6)),(1,(2,5)),(2,(3,4))]$

def dfs$\_$visit$($a$,$ u$,$ color, d$,$ f$,$ time, result$)$:d$[$u$]=$ time$[0]$for v in a$[$u$]$: dfs$\_$visit$($a$,$ v$,$ color, d$,$ f$,$ time, result$)$time$[0]+=1$result.append$(($u$,($d$[$u$],$ f$[$u$])))$

def dfs$($a$)$:d $=[0]*\backslash$ len$($a$)$time $=[0]$# Start DFS from node $0$ dfs$\_$visit$($a$,0,$ color, d$,$ f$,$ time, result$)$Test the DFS function

adj$\_$list $=[[1],[2],[0]]$

print$($dfs$($adj$\_$list$))$ #Output should be $[(0,(1,6)),(1,(2,5)),(2,(3,4))]$

$[(2,(3,4)),(1,(2,5)),(0,(1,6))]$

$(10$ points$)$ Finding cyclesWrite a function that returns whether a node is part of a cycle.

HINT: Modify you DFS to return early when it finds a cycle