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

Question

I'm trying to implement DFS, however, according to A StackOverFlow link about DFS, a DFS uses only Stack.

This is my current implementation:

def DFS_graph_recursive(graph, start, end, stack):
    #Stack to push the node when we are entering the node
    stack.append(start)
    while(end not in stack):
        for i in graph.edges[start]:
            #check if this is inside the stack, to make sure that it doesn't try to go back
            if (i not in stack):
                #Recursive Call
                DFS_graph_recursive(graph, i, end, stack)
        #Pop the stack when we are leaving this node, but need to make sure if end is inside
    if(end not in stack):
        stack.pop()

There is a few issues, the time complexity does not look like O(|E|). The first while loop is O(|E|), however, I need to check whether if my next node is already inside the stack, to avoid going backwards, if this stack is large, and I assume that i not in stack takes O(n) to compute, making this algorithm look like O(|E|^2) in complexity.

The if(end not in stack), makes the algorithm worse in terms of time complexity, since for each edge search, it needs to check if end is in the stack, meaning we don't want to pop the stack if we found a solution. This furthermore increases time complexity to O(|E|^2 + |E|). Is there a way to do this with only one while loop?

In terms of space complexity, it should be O(|V|) worst case that we have a long tree with a branching factor of 1.

I can easily implement a O(|E|) solution if it was a binary tree type, that has a directed path going down to children nodes. The issue is that since the problem is a undirected graph, let's say there are two vertexes, A and B. If A connect to B, then B connect to A. So if I don't check if (i not in stack) I will be stuck going back and forth from A to B, B to A... etc

I don't, but I need to keep track of the paths, plus it guarantees that it doesn't let me go back and forth between two nodes. — user1157751, Jul 17 '15 at 06:05
How do you plan on tracking paths? If you really want that you can push the encountered nodes into a global list. — hyades, Jul 17 '15 at 06:09
The stack is basically tracking paths. A global path is not the right way to go, since the time complexity haven't changed. — user1157751, Jul 17 '15 at 06:16
In the "standard textbook description" of the algorithm nodes have a *colour* associated to them. You first mark them white before running the algorithm them you mark them grey when popping them out of the queue. When you finish the loop for a certain node you mark it black. Whenever you pop a node from the queue you check its colour. If it is not white you have already visited it and you can ignore it. If it is grey you know that you have found a loop. Checking the colour is obviously O(1) and marking all the nodes adds only O(|V|) so complexity doesn't increase. — Bakuriu, Jul 17 '15 at 06:24

hyades · Accepted Answer · 2015-07-17T06:23:34.640

Using this algorithm, you will actually end up going to the same node multiple number of times (The complexity of i not in stack is an added concern)

You should consider keeping a visited list/dictionary, to keep track of nodes you have visited. If you have visited the node, then you wont be pushing that in stack. Code would be like -

vis = {}
def DFS_graph(graph, start, end, stack):
    #Stack to push the node when we are entering the node
    stack.append(start)
    vis[start] = 1
    while len(stack):
        # got to an element
        found_element = stack[-1]
        if found_element == end:
            # you found the end, so break now
            break
        stack.pop()
        for i in graph.edges[start]:
            #check if this is inside the stack, to make sure that it doesn't try to go back
            if i not in vis:
                #Recursive Call
                stack.push(i)

Here I use a dictionary, whose actually complexity of doing a if i not in vis should be O(n) in worst case and O(1) in average case. If you represent your graph nodes as g[0], g[1], g[2] ...., then you can make the complexity into O(1) worst case using a list.

Is there a way to do it without a visited list/dictionary? Won't you be adding in space complexity? It was O(|E|) with a stack, but now it looks like O(|E|+|V|) due to the extra space you had to keep for the visited nodes. — user1157751, Jul 17 '15 at 17:34
@user1157751 you would be pushing vertices or nodes onto the stack and not edges. So worst case space complexity is O(|V|)(for visited array) + O(|V|)(for stack) = O(|V|) — hyades, Jul 19 '15 at 05:17

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

1 Answers1