1. Backtracing

所有排列组合的问题几乎都可以用backtracing算法来解决。

一个非常非常非常重要的算法--backtracing,回溯法,一定要掌握！！！这篇文章给了我非常非常大的帮助。

Backtracing是用递归来枚举多维度值(n-tuple)的算法, 一句话总结其核心就是对于每个维度，依次枚举每一个candidates，然后继续下一个维度。下面是其框架：

void backtrack(int dimension)
{
    /*递归的终止条件 */
    if ( solution[] 符合终止条件 )
    {
        check and record solution;
        return;
    }

    /* 对于该维度，枚举每一个candidates，并返回下一个维度 */
    for ( x = each value of current candidates )
    {
        solution[dimension] = x;
        backtrack( dimension + 1 );
    }
}

例如从1~3选任意2个数，右那些种可能？（可重复选），那么终止条件就是solutin长度为2的时候终止，每个位置上都枚举各个候选者。

不同的问题终止条件可能不同，枚举的时候可能也有限制。等我做到的时候再总结。

一个典型的backtracing函数会有如下几个参数： void backtracing(vector<int> nums, int dim, vector<vector<int> > &records, vector<int> &solution)

nums: original input
dim: the current dimension
records: all the results so far
solution: generated from the current dimension

2. DFS

Depth-First search is a specific form of backtracking related to searching tree or graph structures.

Permutation Subsets等问题也是可以用DFS来解的，比backtracing更容易理解，而且因为DFS在graph tree相关问题里面用的也比较多，所以更要掌握，理解，不惧！

这有一篇关于DFS和BFS的文章，讲得很详细。

DFS模板：

/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[out] path 当前路径，也是中间结果
* @param[out] result 存放最终结果
* @param[inout] cur or gap 标记当前位置或距离目标的距离
* @return 路径长度，如果是求路径本身，则不需要返回长度
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
    if (数据非法) return 0; // 终止条件
    if (cur == input.size()) { // 收敛条件
    // if (gap == 0) {
        将path 放入result
    }
    if (可以剪枝) return; //if(visited[x][y] == true) return;  // 判重
    for(...) { // 执行所有可能的扩展动作
        执行动作，修改path
        dfs(input, step + 1 or gap--, result);
        恢复path
    }
}

3. 图的DFS遍历

非递归用栈实现。 BFS是从queue里面弹出来的时候输出，DFS是push到stack的时候输出

Node structure：

struct DirectedGraphNode {
     int val;
     vector<DirectedGraphNode*> neighbors;
     DirectedGraphNode(int x) {
         val = x;
     }
 };

//给定边的vector，构造Graph
vector<DirectedGraphNode*> CreateDirectedGraph(vector<pair<int, int> > connections) {
     unordered_map<int, DirectedGraphNode*> nodes;
     vector<DirectedGraphNode*> result;
     if (connections.empty()) return result;
     for (auto const& conn : connections) { 
         /*
         DirectedGraphNode *node1, *node2;
         if(nodes.find(conn.first) != nodes.end()) {
             node1 = nodes[conn.first];
         }
         else {
             node1 = new DirectedGraphNode(conn.first);
         }
         if (nodes.find(conn.second) != nodes.end()) {
             node2 = nodes[conn.second];
         }
         else {
             node2 = new DirectedGraphNode(conn.second);
         }
         node1->neighbors.emplace_back(node2);
         */
         //用上面注释的代码更好
         nodes.emplace(conn.first, new DirectedGraphNode(conn.first));
         nodes.emplace(conn.second, new DirectedGraphNode(conn.second));
         auto node1 = nodes[conn.first];
         auto node2 = nodes[conn.second];
         node1->neighbors.emplace_back(node2);       
     }
     for (auto const& v : nodes) {
         result.emplace_back(v.second);
     }
     return result;
 }
//递归写法
 void dfsGraphHelper(DirectedGraphNode *node, unordered_set<DirectedGraphNode*> &is_visted) {
     cout << node->val << endl;
     is_visted.emplace(node);
     for (auto const& v : node->neighbors) {
         if (is_visted.find(v) == is_visted.end()) {
             dfsGraphHelper(v, is_visted);
         }
     }
 }

 //iteration Iteration
 //用个栈，没被访问过入栈，入栈时输出，所有邻居node都被访问过了pop
 void dfsGraphHelperIteration(DirectedGraphNode *node, unordered_set<DirectedGraphNode*> &is_visted) {
     stack<DirectedGraphNode*> stk; 
     stk.push(node);
     cout << node->val << endl;
     is_visted.emplace(node);
     while (stk.empty() == false) {
         DirectedGraphNode *cur = stk.top();
         bool all_visited = true;
         for (auto const& v : cur->neighbors) {
             if (is_visted.find(v) == is_visted.end()) {
                 stk.push(v);
                 cout << v->val << endl;
                 is_visted.emplace(v);
                 all_visited = false;
                 break;//找到一个没访问过的就要break，不然就不是DFS了
             }
         }
         if (all_visited) {
             stk.pop();
         }
     }

 } 

 void dfsGraph(vector<DirectedGraphNode*> graph) {
     unordered_set<DirectedGraphNode*> is_visted;
     //可能是不连通图，所以要从每个没被访问的节点开始做DFS
     for (auto const& node : graph) {
         if (is_visted.find(node) == is_visted.end()) {
             //dfsGraphHelper(node, is_visted);
             dfsGraphHelperIteration(node, is_visted);
         }
     }
 }

4. 图的BFS遍历

用queue实现。

 void bfsGraphHelper(DirectedGraphNode *node, unordered_set<DirectedGraphNode*> &is_visted) {
     queue<DirectedGraphNode*> que;
     que.emplace(node);
     is_visted.emplace(node);
     while (que.empty() == false) {
         DirectedGraphNode *cur = que.front();
         que.pop();
         cout << cur->val << endl;//BFS是从queue里面弹出来的时候输出，DFS是push到stack的时候输出
         for (auto const& v : cur->neighbors) {
             if (is_visted.find(v) == is_visted.end()) {
                 que.emplace(v);
                 is_visted.emplace(v);
             }
         }
     }
 }

5. 判断图上两个节点是否存在path

从start出发开始DFS或者BFS，把之前输出的地方改成判断是否到达end节点。

//DFS递归实现
bool isReachableHelper(DirectedGraphNode *start, DirectedGraphNode *end, unordered_set<DirectedGraphNode*> is_visited) {
     if (start == end) return true;
     is_visited.emplace(start);
     for (auto const& v : start->neighbors) {
         if (is_visited.find(v) == is_visited.end()) {
             if (isReachableHelper(v, end, is_visited)) {
                 return true;
             }
         }
     }
     return false;
 }

 bool isReachable(DirectedGraphNode *start, DirectedGraphNode *end) {
     unordered_set<DirectedGraphNode*> is_visited;
     return isReachableHelper(start, end, is_visited);
 }

 bool isReachable(vector<DirectedGraphNode*> &graph, int v_start, int v_end) {
     DirectedGraphNode *start = NULL;
     DirectedGraphNode *end = NULL;
     for (auto const & v : graph) {
         if (v->val == v_start) {
             start = v;
         } 
         if (v->val == v_end) {
             end = v;
         }
     }
     if (start == NULL || end == NULL) return false;
     return isReachable(start, end);
 }

DFS iteration 实现

 bool isReachable(DirectedGraphNode *start, DirectedGraphNode *end) {
     unordered_set<DirectedGraphNode*> is_visited;
     //return isReachableHelper(start, end, is_visited);
     stack<DirectedGraphNode*> stk;
     if (start == end) return true;
     stk.emplace(start);
     while (!stk.empty()) {
         DirectedGraphNode *cur = stk.top();
         bool all_visited = true;
         for (auto const& v : cur->neighbors) {             
             if (is_visited.find(v) == is_visited.end()) {
                 if (v == end) return true;
                 stk.emplace(v);
                 all_visited = false;
                 break;
             }
         }
         if (all_visited) stk.pop();
     }
     return false;
 }

BFS 实现

bool isReachable(DirectedGraphNode *start, DirectedGraphNode *end) {
     unordered_set<DirectedGraphNode*> is_visited;
     //return isReachableHelper(start, end, is_visited);
     queue<DirectedGraphNode*> que;
     que.emplace(start);
     is_visited.emplace(start);
     while (!que.empty()) {
         DirectedGraphNode *cur = que.front();
         que.pop();
         if (cur == end) return true;//输出时判断
         for (auto const& v : cur->neighbors) {
             if (is_visited.find(v) == is_visited.end()) {                 
                 is_visited.emplace(v);
                 que.emplace(v);
             }
         }
     }     
     return false;
 }

6. 输出两个node之间的所有path

上个问题的follow up，在DFS的时候要保存状态is_visited（跟上个问题一样），但同时也要保存path （当前path）和all_paths（所有路径）。

 void GetPathsDfs(DirectedGraphNode *start, DirectedGraphNode *end, unordered_set<DirectedGraphNode*> &is_visited,
     vector<DirectedGraphNode*> &path, vector<vector<DirectedGraphNode*> > &all_paths) {
     if (start == end) {//收敛条件
         all_paths.emplace_back(path);
         return;
     }
     is_visited.emplace(start);//更新状态
     for (auto const& v : start->neighbors) {//状态转移
         if (is_visited.find(v) == is_visited.end()) {
             path.emplace_back(v);//记录路径
             GetPathsDfs(v, end, is_visited, path, all_paths);//递归
             path.pop_back();//back tracing
         }
     }
 }
 vector<vector<DirectedGraphNode*> > GetPaths(DirectedGraphNode *start, DirectedGraphNode *end) {
     vector<vector<DirectedGraphNode*> > all_paths;
     vector<DirectedGraphNode*> path;
     unordered_set<DirectedGraphNode*> is_visited;
     if (start == NULL || end == NULL) return all_paths;
     path.emplace_back(start);
     GetPathsDfs(start, end, is_visited, path, all_paths);
     return all_paths;
 }

7. 判断图是否存在cycle

DFS，记录下recursion stack里面的node，如果当前结点在栈里，说明存在回路了。

 bool isCyclicHelper(DirectedGraphNode *node, unordered_set<DirectedGraphNode*> &is_visited,
     unordered_map<DirectedGraphNode*, bool> &cur_stk) {
     is_visited.emplace(node);//mark node as visisted
     cur_stk[node] = true; //node now is in the current recursion stack
     for (auto const& neighbor : node->neighbors) {
         //if neighbor is not visited, recursively call helper
         if (is_visited.find(neighbor) == is_visited.end()) {
             if (isCyclicHelper(neighbor, is_visited, cur_stk)) {
                 return true;
             }
         }//elese, check if it is in the recursion stack
         else if (cur_stk.find(neighbor) != cur_stk.end() && cur_stk[neighbor] == true) {
             return true;
         }
     }
     cur_stk[node] = false; //node is NOT in the recursion stack any more
     return false;
 }
 bool isCyclic(vector<DirectedGraphNode*> &graph) {
     unordered_set<DirectedGraphNode*> is_visited;
     unordered_map<DirectedGraphNode*, bool> cur_stk; //if a given in the curren stack or not
     for (auto const& node : graph) {
         if (is_visited.find(node) == is_visited.end() && isCyclicHelper(node, is_visited, cur_stk)) {
             return true;
         }
     }
     return false;
 }

Backtracing DFS BFS