Find all BFS/DFS traversals

Question

Given an undirected cyclic graph, I want to find all possible traversals with Breadth-First search or Depth-First search. That is given a graph as an adjacency-list:

A-BC
B-A
C-ADE
D-C
E-C

So all BFS paths from root A would be:

{ABCDE,ABCED,ACBDE,ACBED}

and for DFS:

{ABCDE,ABCED,ACDEB,ACEDB}

How would I generate those traversals algorithmically in a meaningful way? I suppose one could generate all permutations of letters and check their validity, but that seems like last-resort to me.

Any help would be appreciated.

Answer 1

Apart from the obvious way where you actually perform all possible DFS and BFS traversals you could try this approach:

Step 1. In a dfs traversal starting from the root A transform the adjacency list of the currently visited node like so: First remove the parent of the node from the list. Second generate all permutations of the remaining nodes in the adj list.

So if you are at node C having come from node A you will do:

C -> ADE transform into C -> DE transform into C -> [DE, ED]

Step 2. After step 1 you have the following transformed adj list:

A -> [CB, BC]
B -> []
C -> [DE, ED]
D -> []
E -> []

Now you launch a processing starting from (A,0), where the first item in the pair is the traversal path and the second is an index. Lets assume we have two queues. A BFS queue and a DFS queue. We put this pair into both queues.

Now we repeat the following, first for one queue until it is empty and then for the other queue.

We pop the first pair off the queue. We get (A,0). The node A maps to [BC, CB]. So we generate two new paths (ACB,1) and (ABC,1). Put these new paths in the queue.

Take the first one of these off the queue to get (ACB,1). The index is 1 so we look at the second character in the path string. This is C. Node C maps to [DE, ED].

• The BFS children of this path would be (ACBDE,2) and (ACBED,2) which we obtained by appending the child permutation.
• The DFS children of this path would be (ACDEB,2) and (ACEDB,2) which we obtained by inserting the child permutation right after C into the path string.

We generate the new paths according to which queue we are working on, based on the above and put them in the queue. So if we are working on the BFS queue we put in (ACBDE,2) and (ACBED,2). The contents of our queue are now : (ABC,1) , (ACBDE,2), (ACBED,2).

We pop (ABC,1) off the queue. Generate (ABC,2) since B has no children. And get the queue : (ACBDE,2), (ACBED,2), (ABC,2) and so on. At some point we will end up with a bunch of pairs where the index is not contained in the path. For example if we get (ACBED,5) we know this is a finished path.

Answer 2

BFS is should be quite simple: each node has a certain depth at which it will be found. In your example you find A at depth 0, B and C at depth 1 and E and D at depth 2. In each BFS path, you will have the element with depth 0 (A) as the first element, followed by any permutation of the elements at depth 1 (B and C), followed by any permutation of the elements at depth 2 (E and D), etc... If you look at your example, your 4 BFS paths match that pattern. A is always the first element, followed by BC or CB, followed by DE or ED. You can generalize this for graphs with nodes at deeper depths. To find that, all you need is 1 Dijkstra search which is quite cheap.

In DFS, you don't have the nice separation by depth which makes BFS straightforward. I don't immediately see an algorithm that is as efficient as the one above. You could set up a graph structure and build up your paths by traversing your graph and backtracking. There are some cases in which this would not be very efficient but it might be enough for your application.