图论——深度优先搜索

大家好，欢迎来到IT知识分享网。

图论——深度优先搜索

什么是深度优先搜索：

深度优先搜索的算法

深度优先搜索的应用举例

1.全排列

#include <stdio.h> #include <stdlib.h> int nums[4]={ 
   3,8,9,1}; int book[4]={ 
   0}; int results[24][4]; int result[4]; int N=0; void DFS(int step,int n) { 
    int i=0; if(step==n) { 
    //将这一次搜索到的结果加入结果集  for(i=0;i<4;i++) { 
    results[N][i]=result[i]; } N++; return; } for(i=0;i<4;i++) { 
    if(book[i]==0) { 
    result[step]=nums[i]; book[i]=1; DFS(step+1,n); book[i]=0; result[step]=0; } } } main() { 
    DFS(0,4); int i,j; for(i=0;i<24;i++) { 
    for(j=0;j<4;j++) { 
    printf("%d",results[i][j]); } printf("\n"); } } 

对上述获取全排列的DFS算法我们做以下描述：
首先在全局定义结果集数组和结果数组，用来保存每一次搜索的结果
并且额外地定义了一个很重要的book数组来记录目前结果中哪些数被用到了，以保证不会重复查找一样的数。
DFS算法使用递归的形式实现，在递归的头部，我们先判断本次搜索的步数step是否达到我们预期的步数，也就是我们期望进行全排列的数的个数，这里是4，如果step达到4的话，我们就结束本次搜索，将本次搜索到的结果result加入到结果集results中；如果没有达到预期的步数，那我们就继续进行搜索，搜索的方式是：通过循环依次遍历每一个元素，查看它是否已经在本次搜索中被使用，如果有，那么跳过它继续遍历下一个元素，如果没有，那么将它加入到本次搜索的结果中，同时在book数组中将它标记为已被搜索，然后继续调用DFS进行下一步的搜索，这里通过在DFS形参中传递step+1来表示步数的递增。值得注意的是，在一次对DFS的调用完成并返回时，我们需要在DFS调用的后面将之前进行的操作还原，这样的操作其实可以被称为回溯，这里的具体进行回溯的操作有两个，一个是将刚才book数组中标记为已经搜索的元素还原为未被搜索的状态，同时将刚才把这个元素加入结果的操作还原，当然这一步完全可以省略，因为即便不将这个元素删除也会被下一个元素覆盖。

2.图的最短路径

1.简单的走迷宫算法
假设我们通过二维数组给出一张迷宫地图，其中元素为1的位置表示有障碍不能通过，元素为0的位置表示可以通过，我们在迷宫中任意给出两个元素为0的位置分别表示起点和终点，通过DFS算法来寻找终点和起点之间的最短路径并显示这条路径和最短路径的步数。

#include <stdio.h> #include <stdlib.h> #define N 8 int map[N][N]={ 
   0,0,0,1,1,0,1,1, 1,0,1,0,0,1,1,1, 0,0,0,0,0,0,0,0, 1,1,1,0,1,0,1,0, 0,0,0,0,1,0,1,1, 1,0,1,1,1,0,1,1, 1,0,0,0,0,0,1,0, 1,1,1,0,1,1,1,1, };//迷宫地图  int book[N][N]={ 
   0};//当前路径记录 int min_path[N][N]={ 
   0};//记录最短路径  int min_step=;//最小路径，初始默认为很大 void book_min_path(int [][N],int [][N]); void DFS(int x,int y,int endx,int endy,int step) { 
    if(x==endx&&y==endy) { 
    if(step<min_step) { 
    min_step=step; book_min_path(book,min_path); } return; } int direction[4][2]={ 
   { 
   0,1},{ 
   0,-1},{ 
   1,0},{ 
   -1,0}};//定义方向数组，用以表示每一步的移动方向 int i,j,k,nextx,nexty; for(i=0;i<4;i++) { 
    nextx=x+direction[i][0]; nexty=y+direction[i][1]; if(map[nextx][nexty]!=1&&book[nextx][nexty]!=1&&nextx>=0&&nexty>=0&&nextx<N&&nexty<N)// 下一位置不越界并且可通过  { 
    book[nextx][nexty]=1; DFS(nextx,nexty,endx,endy,step+1); book[nextx][nexty]=0; } } } book_min_path(int book[][N],int min_path[][N])//将最短路径更新  { 
    int i,j; for(i=0;i<N;i++) { 
    for(j=0;j<N;j++) { 
    min_path[i][j]=book[i][j]; } } } Show_min_path() { 
    int i,j; printf("最短路径显示如下：\n"); for(i=0;i<N;i++) { 
    for(j=0;j<N;j++) { 
    if(map[i][j]==1) { 
    printf("@ "); } else if(min_path[i][j]==1) { 
    printf("* "); } else printf(" "); } printf("\n"); } } main() { 
    int i,j,k,startx,starty,endx,endy; printf("地图坐标范围为：(1,1)---(%d,%d)\n",N,N); printf("请输入起点：\n"); scanf("%d %d",&startx,&starty) ; printf("请输入终点：\n"); scanf("%d %d",&endx,&endy) ; book[startx-1][starty-1]=1; DFS(startx-1,starty-1,endx-1,endy-1,0); printf("最短路径为: %d\n",min_step); Show_min_path(); } 

在这个应用中，DFS的算法思路是对每一个位置上下左右四条路径的搜索，且每次搜索都是递进连续的，除非到达终点或者碰到死胡同才开始折回，也就是回溯。
对于四个探索方向的变更，我们通过定义了一个方向数组来实现这样的功能，这是一个四行两列的数组，每一行都代表对一个方向的探索，其中每一行中的两个元素始终有一个是0，另一个为1或-1，并且每一行不相重复，这样我们通过列的循环让x和y分别去加上每一行的第一个元素和第二个元素，这样的结果是，每一次循环相加都会使x和y中的一个发生+1或者-1的变化而另一个保持不变，在图中也就代表了向某一个方向的一次移动。
探索的思路和上一个算法一样都是相同的套路，即就是如果下一个探索的目标可以被探索，那么就将其进行一些标记和相关操作，然后进行下一步的探索，并在下一步探索返回时还原这样的操作，也就是回溯操作。如果我们新探查到了一条可以从起点通向终点的路径，那么我们将这条路径所花费的步数和当前的最小步数相比较，如果这条新路径的步数更少，那么我们就更新最小步数的值，并将记录的最小路径更新呢为这条路径的位置。

注意：对于求解图的最短路径问题来说，当图的规模很大，存在的路径很多很多时，DFS绝对不算是一种好的求解算法，因为为了求解最短路径，我们必须将所有可能的路径全部查找出来，这时很耗费代价的，当问题的规模大到一定程度时，不加优化的DFS查找耗费的时间代价有可能是令人难以接受的，它将是某一常数的指数级增长，很多情况下甚至是永远也运行不完的。

3.砝码称重

本题每一种解的情况并不一定是在最大深度出产生，但是仍然可以用DFS来求解，因为每一种结果必定在达到最深路径的过程中产生，值得注意的是，我们在搜索时还需要考虑砝码重量相减的情况，所以每一次可以进行两次DFS，分别对相加和相减的情况进行求解，这是和之前有所区别的。我们每一次搜索到一个砝码重量元素时，都有两种选择，一种是用当前的质量和去加上这个砝码，第二种则是减去这个砝码，当然其结果都将是绝对值的形式。对于这两种情况我们选择分别去求解，并且分别对这两种情况获得的新值进行判断，如果之前没有获得过这样的值，那么将该值添加到结果集当中。然后对于这两种情况得到的两个新的砝码总和值，我们分别将其作为两次DFS的参数传入，从而再进行两次DFS进行继续查找。直到每次查找用完了所有砝码，也就是达到了最大深度为止。

#include<stdio.h>  #include<stdlib.h> int results[]={ 
   0};//初始化定义结果集 int num;//当前获得的结果总数 DFS(int elements[],int step,int result,int N,int book[]) { 
    if(step==N)//如果搜索达到最大深度则返回 { 
    return; } int i,j,k,t1,t2; int Sresult=result,Dresult=result; for(i=0;i<N;i++) { 
    if(book[i]!=1) { 
    //t1,t2分别用于临时寄存砝码和与砝码差的值，用于回溯时将原值归位 t1=Sresult; t2=Dresult; Sresult=abs(Sresult+elements[i]); Dresult=abs(Dresult-elements[i]); if(results[Sresult]==0) { 
    num++; results[Sresult]=1; } if(results[Dresult]==0) { 
    num++; results[Dresult]=1; } book[i]=1; DFS(elements,step+1,Sresult,N,book); DFS(elements,step+1,Dresult,N,book); book[i]=0; //将两个值进行归位 Sresult=t1; Dresult=t2; } } } main() { 
    int N,i,j,k=0; scanf("%d",&N); int elements[N]; int book[N]; for(i=0;i<N;i++) { 
    scanf("%d",&elements[i]); } DFS(elements,0,0,N,book); printf("\n"); for(i=0;;i++) { 
    if(results[i]==1) { 
    if(i!=0) printf("%d ",i); k++; if(k==num) { 
    break; } } } }