C++ 深度优先搜索

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。

首先将根节点放入stack中。
从stack中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜寻并回传结果。否则将它某一个尚未检验过的直接子节点加入stack中。
重复步骤2。
如果不存在未检测过的直接子节点。
将上一级节点加入stack中。
重复步骤2。
重复步骤4。
若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

#include <iostream>
using namespace std;
int startx,starty,endx,endy;
int mi=999999;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int m[100][100],v[100][100];
bool found=false;
void DFS(int x,int y,int step){
    if(x==endx&&y==endy) {mi=min(step,mi);found=true;return;}
    else{
        for(int k=0;k<4;k++){
            int nextx=x+dx[k];
            int nexty=y+dy[k];
            if(m[nextx][nexty]==1&&v[nextx][nexty]==0){
                v[nextx][nexty]=1;
//              printf("I found %d %d and step here is %dn",nextx,nexty,step+1);
                DFS(nextx,nexty,step+1);
                v[nextx][nexty]=0;
            }
        }
    }
}
int main(){
    int a,b;
    cin >> a >> b;
    int nu;
    for(int i=1;i<=a;i++) for (int j=1;j<=b;j++) {cin >> nu;m[i][j]=nu+1;}
    cin >> startx >> starty >> endx >> endy;
    v[startx][starty]=1;
    DFS(startx,starty,0);
    if(found==true) cout << mi << endl;
    else cout << "Not Found" << endl;
    return 0;
}

コメント