python - DFS - Implementing a O(|E|) timing complexity solution -

i'm trying implement dfs, however, according a stackoverflow link dfs, dfs uses stack.

this current implementation:

def dfs_graph_recursive(graph, start, end, stack):     #stack push node when entering node     stack.append(start)     while(end not in stack):         in graph.edges[start]:             #check if inside stack, make sure doesn't try go             if (i not in stack):                 #recursive call                 dfs_graph_recursive(graph, i, end, stack)         #pop stack when leaving node, need make sure if end inside     if(end not in stack):         stack.pop() 

there few issues, time complexity not o(|e|). first while loop o(|e|), however, need check whether if next node inside stack, avoid going backwards, if stack large, , assume i not in stack takes o(n) compute, making algorithm o(|e|^2) in complexity.

the if(end not in stack), makes algorithm worse in terms of time complexity, since each edge search, needs check if end in stack, meaning don't want pop stack if found solution. furthermore increases time complexity o(|e|^2 + |e|). there way 1 while loop?

in terms of space complexity, should o(|v|) worst case have long tree branching factor of 1.

i can implement o(|e|) solution if binary tree type, has directed path going down children nodes. issue since problem undirected graph, let's there 2 vertexes, , b. if connect b, b connect a. if don't check if (i not in stack) stuck going , forth b, b a... etc

using algorithm, end going same node multiple number of times (the complexity of i not in stack added concern)

you should consider keeping visited list/dictionary, keep track of nodes have visited. if have visited node, wont pushing in stack. code -

vis = {} def dfs_graph(graph, start, end, stack):     #stack push node when entering node     stack.append(start)     vis[start] = 1     while len(stack):         # got element         found_element = stack[-1]         if found_element == end:             # found end, break             break         stack.pop()         in graph.edges[start]:             #check if inside stack, make sure doesn't try go             if not in vis:                 #recursive call                 stack.push(i) 

here use dictionary, complexity of doing if not in vis should o(n) in worst case , o(1) in average case. if represent graph nodes g[0], g[1], g[2] ...., can make complexity o(1) worst case using list.