如何实现图的深度优先和广度优先搜索？

0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6

const int MAXN = 7;

void dfs(int u) {
    if(visit[u]) {                                // 1
        return ;
    }
    visit[u] = true;                              // 2
    dfs_add(u);                                   // 3
    for(int i = 0; i < MAXN; ++i) {
        int v = i;
        if(adj[u][v]) {                           // 4
            dfs(v);                               // 5
        }
    }
}

void dfs_add(int u) {
    ans[ansSize++] = u;
}

bool adj[MAXN][MAXN] = {
    {0, 1, 1, 0, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 0},
    {1, 0, 0, 0, 0, 1, 1},
    {0, 1, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 1, 0},
    {0, 0, 1, 0, 1, 0, 0},
    {0, 0, 1, 0, 0, 0, 0},
};

int dfs(int n) {
    return !n ? 1 : n * dfs(n-1);
}

int dfs(unsigned int n) {
    if(n <= 1) {
        return 1;
    }
    return dfs(n-1) + dfs(n-2);
}

void dfs(int depth) {                                  // 1
    if(depth == MAXN) {                                // 2
        dfs_print();
        return;
    }
    for(int i = 1; i <= MAXN; ++i) {
        int v = i;
        if(!visit[v]) {                                // 3
            dfs_add(v);                                // 4             
            dfs(depth+1);
            dfs_dec(v);
        }
    }
}

void dfs_add(int u) {
    visit[u] = true;
    ans[ansSize] = u;
    ++ansSize;
}

void dfs_dec(int u) {
    --ansSize;
    visit[u] = false;
}

public class DepthFirstSearch { 
//索引代表顶点，值表示当前顶点是否已经被搜索 
private boolean[] marked; 
//记录有多少个顶点与s顶点相通 
private int count; 
//构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点 
public DepthFirstSearch(Graph G,int s){ 
//创建一个和图的顶点数一样大小的布尔数组 marked = new boolean[G.V()]; 
//搜索G图中与顶点s相同的所有顶点 dfs(G,s); }
//使用深度优先搜索找出G图中v顶点的所有相邻顶点 
private void dfs(Graph G, int v){ //把当前顶点标记为已搜索 marked[v]=true; 
//遍历v顶点的邻接表，得到每一个顶点w for (Integer w : G.adj(v)){ 
//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 
if (!marked[w]){ dfs(G,w); } }//相通的顶点数量+1 count++; }//判断w顶点与s顶点是否相通 
public boolean marked(int w){ return marked[w]; }//获取与顶点s相通的所有顶点的总数 
public int count(){ return count; } }

public class BreadthFirstSearch { 
//索引代表顶点，值表示当前顶点是否已经被搜索 
private boolean[] marked; 
//记录有多少个顶点与s顶点相通 
private int count; 
//用来存储待搜索邻接表的点 private Queue<Integer> waitSearch; 12345678
//构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点 
public BreadthFirstSearch(Graph G, int s) { 
//创建一个和图的顶点数一样大小的布尔数组 
marked = new boolean[G.V()]; 
//初始化待搜索顶点的队列 
waitSearch = new Queue<Integer>(); 
//搜索G图中与顶点s相同的所有顶点 
dfs(G, s); }
//使用广度优先搜索找出G图中v顶点的所有相邻顶点 
private void dfs(Graph G, int v) { 
//把当前顶点v标记为已搜索 
marked[v]=true; 
//把当前顶点v放入到队列中，等待搜索它的邻接表 
waitSearch.enqueue(v); 
//使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表 
while(!waitSearch.isEmpty()){ Integer wait = waitSearch.dequeue(); 
//遍历wait顶点的邻接表，得到每一个顶点w for (Integer w : G.adj(wait)) { //如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 if (!marked[w]) { dfs(G, w); } } }//相通的顶点数量+1 count++; }//判断w顶点与s顶点是否相通 public boolean marked(int w) { return marked[w]; }//获取与顶点s相通的所有顶点的总数 public int count() { return count; } }

 满足如下条件的序列 X（序列中元素被标号为 1、2、3…m）被称为“加成序列”：
 X[1]=1
 X[m]=n
 X[1]<X[2]<…<X[m−1]<X[m]
 对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得 X[k]=X[i]+X[j]。
 你的任务是：给定一个整数 n，找出符合上述条件的长度 m 最小的“加成序列”。
 如果有多个满足要求的答案，只需要找出任意一个可行解。 n <= 100

 /*
  * @Author: ACCXavier
  * @Date: 2022-01-28 22:29:01
  * @LastEditTime: 2022-01-29 09:20:03
  * Bilibili:https://space.bilibili.com/7469540
  * @keywords: DFS迭代加深
  * 逐步增加搜索层数
  */
 ​
 #include <iostream>
 #include <cstring>
 #include <algorithm>
 ​
 using namespace std;
 const int N = 110;
 int path[N];
 int n;
 //当前层,要搜到的层(从1开始的)
 bool dfs(int u,int depth){
     if(u == depth){
         return path[u - 1] == n;
     }
     bool st[N] = {0};
     for(int i = u - 1; i >= 0; -- i){
         for(int j = i; j >= 0; -- j){//j > i组合搜索
             int s = path[i] + path[j];
                      //保证严格单调递增
             if(s > n || s <= path[u - 1] || st[s])continue;
             st[s] = true;
             path[u] = s;
             if(dfs(u + 1,depth))return true;
         }
     }
     return false;
 }
 int main()
 {
     path[0] = 1;
     
     while(cin >> n,n){
         int depth = 1;
         while(!dfs(1,depth)) ++ depth;//false说明层数不够
         for(int i = 0; i < depth; ++ i)cout << path[i] << ' ';
         cout << endl;
         
     }
 }

 给定 n 本书，编号为 1∼n。
 在初始状态下，书是任意排列的。
 在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。
 我们的目标状态是把书按照 1∼n 的顺序依次排列。
 求最少需要多少次操作。
 如果最少操作次数大于或等于 **5** 次，则输出 5 or more。

 /*
  * @Author: ACCXavier
  * @Date: 2022-01-30 19:51:40
  * @LastEditTime: 2022-01-30 21:01:19
  * Bilibili:https://space.bilibili.com/7469540
  * @keywords: DFS 中等
 我们开一个估计函数这个估计函数的返回值小于等于真实值这样我们就可以利用这个进行最优化减枝
 如果估计函数都无法完成那么真实值一定也无法完成可以直接剪掉
 由于步数很小答案可能会很大所以用迭代加深优化搜索
 枚举选择的长度以及放的位置
 选择书后不用往前放,因为会对应前面的一种选法,重复
 这题由于每次我们最多改变3个后继的位置的关系所以假设我们有tot个错误前后关系那么(tot+2)/3就是我们最多要操作的次数
 我们可以用这个(tot+2)/3来当成估计函数
  */
 #include <iostream>
 #include <cstring>
 #include <algorithm>
 ​
 using namespace std;
 const int N = 15;
 int q[N];
 int w[5][N];//暂存每层u的状态
 int n;
 int f(){//不正确的后继数量
     int cnt = 0;
     for(int i = 0; i < n - 1; ++ i){
         if(q[i + 1] != q[i] + 1)cnt ++;
     }
     return (cnt + 2)/3;//对3上取整
 }
 ​
 bool dfs(int u,int depth){
     if(u + f() > depth)return false;//
     if(!f())return true;//为0表示已经排好
     
     for(int len = 1; len <= n; ++ len){//移动len长度的书
         for(int l = 0; l + len - 1 < n; ++ l){//左端点从0开始,右端点就要-1
             int r = l + len - 1;
 ​
             for(int k = r + 1; k < n; ++ k){//移动到第k位数字的后面,从r + 1位开始
                 //memcpy(str1, str2, size_t n) 从存储区 str2 复制 n 个字节到存储区 str1。
                 memcpy(w[u],q,sizeof q);//暂时存储
                 
                 int x,y;
 ​
                 //y       x 
                 //l______r____k____
                 for(x = r + 1,y = l;x <= k;x ++,y ++)q[y] = w[u][x];
                 //再拷贝前面的一部分,y继续加
                 for(x = l; x <= r; ++ x, ++ y)q[y] = w[u][x];
                 if(dfs(u + 1,depth))return true;
                 memcpy(q,w[u],sizeof q);//回溯
             }
         }
     }
     return false;//! bool类型默认返回值true,很容易造成搜索结果错误!
     //!除了void,都记得写return!
 }
 int main()
 {
     int T;
     cin >> T;
     while(T --){
         cin >> n;
         for(int i = 0; i < n; ++ i){
             cin >> q[i];
         }
         
         int depth = 0;//0次对应已经排好序
         while(depth < 5 && !dfs(0,depth))depth ++;
         
         if(depth == 5)puts("5 or more");
         else printf("%d\n",depth);
     }
     return 0;
 }

 1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
 0

 AC
 2
 DDHH
 2

 /*
  * @Author: ACCXavier
  * @Date: 2022-01-30 20:12:57
  * @LastEditTime: 2022-01-31 10:50:48
  * Bilibili:https://space.bilibili.com/7469540
  * @keywords: DFS 中等
  * 
 ​
 */
 /*
         0     1
         0     1
         2     3
 7 4  5  6  7  8  9  10   2
         11    12
 6 13 14 15 16 17 18 19   3
         20    21
         22    23
         5      4
 */
 ​
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 ​
 using namespace std;
 ​
 const int N = 24;
 //如果op里面用从1开始的编号,那么opposite和center也改成从1开始,q从1输入即可
 int op[8][7] = {
     {0, 2, 6, 11, 15, 20, 22},
     {1, 3, 8, 12, 17, 21, 23},
     {10, 9, 8, 7, 6, 5, 4},
     {19, 18, 17, 16, 15, 14, 13},
     {23, 21, 17, 12, 8, 3, 1},
     {22, 20, 15, 11, 6, 2, 0},
     {13, 14, 15, 16, 17, 18, 19},
     {4, 5, 6, 7, 8, 9, 10}
 };
 ​
 int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
 int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
 ​
 int q[N];
 int path[100];
 ​
 int f()//8 - cnt(最多的数字),<=最小操作步数
 {
     static int sum[4];
     memset(sum, 0, sizeof sum);
     for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;
 ​
     int maxv = 0;
     for (int i = 1; i <= 3; i ++ ) maxv = max(maxv, sum[i]);
 ​
     return 8 - maxv;//!8 - maxv,距离
 }
 ​
 void operate(int x)//操作第x个条
 {
     int t = q[op[x][0]];//正方向第一个
     for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];//循环
     q[op[x][6]] = t;//最后一位
 }
 //当前第u层,上限depth,最后一个操作的编号
 bool dfs(int u, int depth, int last)
 {
     if (u + f() > depth) return false;
     if (f() == 0) return true;
 ​
     for (int i = 0; i < 8; i ++ )
         if (last != opposite[i])//不能做上一步操作的逆操作,无用功
         {
             operate(i);
             path[u] = i;
             if (dfs(u + 1, depth, i)) return true;
             operate(opposite[i]);//回溯
         }
 ​
     return false;
 }
 ​
 int main()
 {
     while (cin >> q[0], q[0])
     {
         for (int i = 1; i < 24; i ++ ) cin >> q[i];
 ​
         int depth = 0;
         while (!dfs(0, depth, -1)) depth ++ ;
 ​
         if (!depth) printf("No moves needed");
         else
         {
             for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
         }
         printf("\n%d\n", q[6]);
     }
 ​
     return 0;
 }

 20 5
 7
 5
 4
 18
 1

 19

 /*
  * @Author: ACCXavier
  * @Date: 2022-01-29 16:26:07
  * @LastEditTime: 2022-01-29 17:07:40
  * Bilibili:https://space.bilibili.com/7469540
  * @keywords: 双向DFS
  * 将物品分两份,前一部分k暴搜出所有方案,再搜后一部分二分<=m的最大值
  */
 #include <iostream>
 #include <cstring>
 #include <algorithm>
 ​
 using namespace std;
 ​
 typedef long long ll;
 ​
 const int N = 46;
 int n,m;//物品数量和承受重量
 int w[N];//每件物品的质量
 int k;//前一部分k个
 int weight[1 << 25],//前k部分的所有方案
     cnt = 1;//已有一种方案,即不选,放在0位,后续搜索的时候都是不选就是只选前半部分,前面也不选那就是全不选
 int ans;
 ​
 //物品序号(从0开始),当前质量和
 void dfs1(int u,int s){
     if(u == k){//从0开始,所以u == k表示已经处理了0~u-1共k个物品
     //!搜到k 不是 n
         weight[cnt ++ ] =  s;
         return;
     }
     if((ll)s + w[u] <= m)dfs1(u + 1,s + w[u]);
     dfs1(u + 1,w1);
 }
 //物品序号(从0开始),当前质量和
 void dfs2(int u,int s){
     if(u >= n){//写>是因为k若取n/2+2可能大于n,等同于边界特判
     //找<=m的最大数,前驱
         int l = 0,r = cnt - 1;
         while(l < r){
             int mid = l + r + 1 >> 1;
             if((ll)sum + weight[mid] <= m)l = mid;
             else r = mid - 1;
         }
         ans = max(ans,sum + weight[l]);
         return;
     }
     dfs2(u + 1,sum);
     if((ll)sum + w[u] <= m)dfs2(u + 1,sum + w[u]);
 }
 int main(){
     cin >> m >> n;
     for(int i = 0; i < n; ++ i){
         cin >> w[i];
     }
     sort(w,w + n,greater<int>());
     k = n / 2 + 2;
     dfs1(0,0);
     //!只需要排序到cnt
     sort(weight,weight + cnt);//二分要用weight,不要倒序排序
     cnt = unique(weight,weight + cnt) - weight;
 ​
     dfs2(k,0);
     cout << ans << endl;
     return 0;
 }
 ​
 ​

Graph_init <- function( glenth)
{
  v = glenth
  adjList <- vector("list", length = v) #生成一个出发顶点出发的所有路径列表
  for (  i in 1:v) {
    adjList[[i]] =list( )          #单个元素列表为该顶点出发的一条路径
  }
 return(list(adjList = adjList,v =v))
}

add_edge <- function(adjList,u,v)
{
  adjList[[u]]=c(adjList[[u]],v)
  return (adjList)
}

printAllPathsUtil <- function( u,  d, isVisited,localPathList,adjList )
{
  if (u == d) {
    tnodes= unlist(localPathList)
    print(tnodes)
    }
  }
  
  #Mark the current node
  isVisited[u] = 1
  #Recur for all the vertices
  #adjacent to current vertex
  for ( i in adjList[[u]]) {   
    if (isVisited[i]==0) {
      localPathList = c(localPathList,i)
      printAllPathsUtil(i, d, isVisited, localPathList,adjList)
      #remove current node
      # in path[]
      localPathList = localPathList[-length(localPathList)]
    }
  }
  #Mark the current node
  isVisited[u] = 0
}

printAllPaths <- function( s,  d, v, adjList )
{
  isVisited = array(data=0,dim=v)
  pathList = list()
  # add source to path[]
  pathList = c(pathList,s)
  #Call recursive utility
  rnum = printAllPathsUtil(s, d, isVisited, pathList,adjList )
   
}

dfs_main <- function ()
{ 
  g = Graph_init(4)
  
  adjList = g$adjList
  v= g$v
  adjList = add_edge(adjList,1, 2)
  adjList = add_edge(adjList,1, 3)
  adjList = add_edge(adjList,1, 4)
  adjList = add_edge(adjList,3, 1)
  adjList = add_edge(adjList,3, 2)
  adjList = add_edge(adjList,2, 4)
  #arbitrary source
  s = 3
  #arbitrary destination
  d = 4
  print(paste0("Following are all different paths from ",s," to ",d) )
  printAllPaths(s, d,  v,adjList)
}