1
$\begingroup$

I often see DFS is used interchangeably with backtracking specially in many permutation, combinations and subset problems. But usually DFS has implicit tree and does backtracking at leaf nodes whereas backtracking is on an implicit tree and does use pruning each branch.

My question is how to systematically think about relating a DFS graph explicit one to building an implicit search space graph?

Here is a backtracking framework:

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        }
        return false
    }
}

Here is a DFS:

procedure DFS(G,v):
     label v as discovered
     for all edges from v to w in G.adjacentEdges(v) do
         if vertex w is not labeled as discovered then
             recursively call DFS(G,w)

Here is DFS used in permutation:

private void dfs(String str, int start, int k, StringBuffer sb, boolean[] marked, List<String> res) {
    if (start == k) {
        res.add(sb.toString());
        return;
    }
    for (int i = 0; i < str.length(); i++) {
        //if element is not visited yet
        if (!marked[i]) {
            //if input string has duplicates, ignore them and continue
            if (i > 0 && str.charAt(i) == str.charAt(i - 1)) {
                continue;
            }
            sb.append(str.charAt(i));
            marked[i] = true;
            // recursively go to next element
            dfs(str, start + 1, k, sb, marked, res);
            sb.deleteCharAt(sb.length() - 1);
            marked[i] = false;
        }
    }
}

how to visualize DFS in a search space rather than in a graph which already exists and interchangeably understand DFS and backtracking.

Search Space Sample for permute (ABC):

         ROOTNODE
       /     |     \
     A       B      C
   /   \    /  \    / \
  B    C    A   C  A   B
  |    |    |   |  |   |
  C    B    C   A  B   A

When i tried to solve myself i usually come up with the recursive solution but i did not start solving by visualizing using a general graph techniques like most solution online.

References:

  1. http://exceptional-code.blogspot.com/2012/09/generating-all-permutations.html
  2. https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning
  3. https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search
  4. https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
  5. http://rangerway.com/way/algorithm-permutation-combination-subset
  6. http://www.dataeng.net/2016/10/generating-all-permutations-of-string.html
$\endgroup$
  • $\begingroup$ Welcome to CS.SE! I can't understand what you are asking. What's a "a DFS graph explicit one"? What do you mean by "building an implicit search space graph"? What are you trying to achieve? Have you read the descriptions of DFS in a textbook (rather than just blog posts)? $\endgroup$ – D.W. Jul 24 '17 at 17:16
  • $\begingroup$ @D.W Thanks, what I mean by it is, if given a graph (explicit meaning using adjacency list) we can use DFS to traverse through the graph like from a start node. But in terms of permutations the DFS solutions consider the search space as graph and the next node here doesn't exist but we think all characters except these characters as next node (implicit).. But I think i finally understand when i try to explain it here. In implicit graph the nodes are states of variables with some values and with some choices and edges are state transitions... $\endgroup$ – Dexters Jul 25 '17 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.