[DFS]求全排列问题

问题：全排列的种树是N!，要求按字典序输出。
思路：我们可以把N个数两两建立无向边（即任意两个结点之间都有边，也就是一个N个结点的完全图），然后对每个点作为起点，分别做一次深度优先遍历，当所有点都已经标记时输出当前的遍历路径，就是其中一个排列，这里需要注意，回溯的时候需要将原先标记的点的标记取消，否则只能输出一个排列。如果要按照字典序，则需要在遍历的时候保证每次遍历都是按照结点从小到大的方式进行遍历的。

image.png

代码：

#include <iostream>
using namespace std;

void dfs(int arr[],int n,int visited[],int i,int out[])
{
    if(i == n)
    {
        for (int j = 0; j < n; ++j) {
            cout<<out[j]<<" ";
        }
        cout<<endl;
    } else{
        for (int j = 0; j < n; ++j) {
            if (visited[j] == 0)
            {
                out[i] = arr[j];
                visited[j] = 1;
                dfs(arr,n,visited,i+1,out);
                visited[j] = 0;
            }
        }
    }

}

int test_FullAranged()
{
    //freopen("in.txt","r",stdin);
    int n = 5;
    int arr[5] = {1,2,3,4,5};
    int visited[5];
    memset(visited,0, sizeof(visited));

    int out[5];

    dfs(arr,n,visited,0,out);

}