CODEWITHSUNDEEP
algorithmsearchdata-structuresgraph-algorithm
Alexander TheGreat
Alexander TheGreat

Reputation: 31

Getting a DFS from a BFS?

Is it possible to get a DFS doing a BFS search? If I just use a stack and then pop them out wouldn't it come out in DFS order?

I am trying to do a DFS search but I only have an adjacency list with outgoing edges, so I don't know how to get the indegree of every vertex.

0: 2,4 1: none 2: 1,3 3: none 4: none

so 0 has outgoing edges to 2 and 4.

I'm kinda lost and thought if I did BFS search using a stack I would get a DFS and then the topological order.

Upvotes: 2

Views: 1019

Answers (2)

AnT stands with Russia
AnT stands with Russia

Reputation: 320777

If you take a classic BFS algorithm and replace the FIFO queue with a LIFO stack, you will indeed get DFS vertex discovery order - so called DFS pre-ordering. I.e. the order in which your algorithm will visit graph vertices for the very first time will be exactly the same as in DFS.

However, this will not give you DFS memory usage and will not give you post-ordering of vertices - other extremely important properties of the classic DFS algorithm (Why is depth-first search claimed to be space efficient?)

In other words, it is completely incorrect to claim that replacing the BFS queue with a stack will turn BFS into DFS. These algorithms in their canonical form have completely different internal structures. What you will obtain through such replacement is a pseudo-DFS algorithm, which will successfully simulate DFS pre-ordering, but will not provide you with DFS post-ordering.

So it is a question of what you are trying to use it for. Do you need DFS post-ordering?

And it looks like you actually do. The classic toposort algorithm is based specifically on using the vertex post-ordering generated by DFS. The toposort order is the order in which the classic DFS algorithm makes its very last visit to each vertex. This immediately means that your pseudo-DFS will not work for that purpose.

There's probably some way to "whip it into submission" and somehow make it work by adding bunch of crutches here and there, but it is simply not worth it. Just take the classic genuine DFS and use it. It will do it in much more simple, elegant and efficient manner.

Upvotes: 0

aa333
aa333

Reputation: 2574

When done iteratively, the only difference between DFS and BFS is the data structure used to store to the vertices that will be processed in future iterations.

Use a queue and you get BFS, use a stack and you get DFS. 

def bfs(g, start):
   discovered = [False] * (len(g) + 1)
   processed = [False] * (len(g) + 1)
   parents = [-1] * (len(g) + 1)
   discovered[start] = True
   q = deque()   #Different line
   q.append(start)
   while len(q) > 0:
    v = q.popleft() #Different line
    print "Visited:" + str(v)
    # process_ve(v)
    nbors = g[v]
    for n in nbors:
        if not p[n]:
            # process_edge((v,n))
            print ((v, n))
        if not discovered[n]:
            discovered[n] = True
            parents[n] = v
            q.append(n)
    # process_vl(v)
    processed[v] = True
    return parents

And DFS:

def dfs(g, start):
   discovered = [False] * (len(g) + 1)
   processed = [False] * (len(g) + 1)
   parents = [-1] * (len(g) + 1)
   discovered[start] = True
   q = list()  #Different line
   q.append(start)
   while len(q) > 0:
    v = q.pop()  #Different line
    print "Visited:" + str(v)
    # process_ve(v)
    nbors = g[v]
    for n in nbors:
        if not processed[n]:
            # process_edge((v,n))
            print ((v, n))
        if not discovered[n]:
            d[n] = True
            pts[n] = v
            q.append(n)
    # process_vl(v)
    processed[v] = True
    return parents

The examples in Python above should make that clear. The only difference between them is that we use a deque (Python's version of queue) in one and a list(Python's version of a stack) in the other.

The examples follow the algorithms as explained in The Algorithm Design Manual by Steve Skiena.

Upvotes: 2

Related Questions