深度优先遍历DFS总结:两种常见的结构 + 全排列

野性酷女 2022-06-03 01:46 166阅读 0赞

在leetcode的题中经常要使用DFS深度优先遍历来求解问题，做得多了就会发现这也是有套路的，我这里总结两个套路，以及对应的输出：

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    /*
    输出如下:
    Size : 0 ,
    Size : 1 , 1
    Size : 2 , 1 2
    Size : 3 , 1 2 3
    Size : 4 , 1 2 3 4
    
    */
    void dfs(vector<int> nums, vector<int> one ,int index)
    {
        cout << "Size : " << one.size() << " , ";
        for (int a : one)
            cout << a << " ";
        cout << endl;
        if (index == nums.size())
        {
            return;
        }
        else
        {
            one.push_back(nums[index]);
            dfs(nums, one, index + 1);
            one.pop_back();
        }
    }
    
    
    /*
    输入如下:
    Size : 0 ,
    Size : 1 , 1
    Size : 2 , 1 2
    Size : 3 , 1 2 3
    Size : 4 , 1 2 3 4
    Size : 1 , 2
    Size : 2 , 2 3
    Size : 3 , 2 3 4
    Size : 1 , 3
    Size : 2 , 3 4
    Size : 1 , 4
    
    */
    void dfs1(vector<int> nums, vector<int> one, int index)
    {
        cout << "Size : " << one.size() << " , ";
        for (int a : one)
            cout << a << " ";
        cout << endl;
        if (index == nums.size())
        {
            return;
        }
        else
        {
            for (int i = index; i < nums.size(); i++)
            {
                one.push_back(nums[i]);
                dfs(nums, one, i + 1);
                one.pop_back();
            }
        }
    }
    
    
    int main()
    {
        vector<int> nums{
       1,2,3,4};
        cout << "DFS1 is Following:" << endl;
        dfs(nums, vector<int>(), 0);
    
        cout << endl << endl << "DFS2 is Following:" << endl;
        dfs1(nums, vector<int>(), 0);
    
    }

输出如下：

![这里写图片描述][SouthEast]

那么总结就很简单了，第一种是做一个从当前元素的遍历，第二个是从每一个元素的遍历，注意可能出现重复。

下面是全排列的另一种做法，直接DFS深度优先遍历的做法，很棒，值得放到一起学习：

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    int countc = 0;
    
    void dfs(vector<bool>& visit, vector<int>& a,int index, int size)
    {
        if (index >= size + 1)
        {
            for (int i = 1; i <=size; i++)
                cout << a[i] << " , ";
            cout << endl;
            countc++;
            return;
        }
        else
        {
            for (int i = 1; i <= size; i++)
            {
                if (visit[i] == false )
                {
                    visit[i] = true;
                    a[index] = i;
                    dfs(visit,a, index + 1, size);
                    visit[i] = false;
                }
            }
        }
    }
    
    
    int main()
    {
        const int size = 4;
        vector<bool> visit(size + 1, false);
        vector<int> a(size + 1, 0);
    
        dfs(visit,a,1,size);
        cout << "一共" << countc << "排列" << endl;
    
    }

执行结果如下

![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220603/a7f2ad07eeb94c289ca4afe9a0a1223c.png
[SouthEast 1]: /images/20220603/38054f4d2de84fca93c437d9ad70ec01.png