搜索算法科普型入门文章--Bfs,Dfs和回溯

Bfs,Dfs和回溯

         Bfs和dfs都是遍历图（包括隐式的状态树）的方法，搜索的策略略有不同，bfs的策略是尽可能往深处搜索。而bfs则是一层一层搜索，搜索完一层所有的节点后，再进入下一层，对于无向图来说，下面给出bfs和dfs的模板

Bfs()

{

         Int head=tail=0;

         int que[N*N+5][2] //此处的队列大小并无强制要求，尽可能大点，第2个维度记录深度（层数）

         used[0]=1;  //标记用过

         que[tail][0]=0;   //从0开始遍历

         que[tail++][1]=0;  //第0层

         while(head

         {

                   cur=que[head][0];

                   curDepth=que[head++][1];

                   used[cur]=1;

for(i=0;i

{

         If(map[i][cur] && !used[i])  //如果存在边（i，cur），并且这个节点没访问过

         {

                   Que[tail][0]=I;

                   Que[tail++][1]=curDepth+1;

}

}

}

}

在bfs过程中可以记录当前节点为第几层的~，因为bfs过程是搜索完一层，才到下一层的~，我们可以对每个节点记录层数（用红色标出）

例题poj1915 Knight Moves

Description

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.

Input

The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

Output

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

Sample Input

3

8

0 0

7 0

100

0 0

30 50

10

1 1

1 1

Sample Output

5

28

0

关键代码：（STL实现）

t.x=x0; t.y=y0;

t.stp=0;

u[x0][y0]=1;

                   Q.clear();

                   Q.push_back(t);

                   while(!Q.empty()) {

                            t=Q.front(); Q.pop_front();

                            if(t.x==x1 && t.y==y1) break; //如果找到目标节点，就跳出

                            for(i=0;i<8;i++) {   //向8个方向搜索

                                     s.x=t.x+d[i][0];

                                     s.y=t.y+d[i][1];

                                     if(s.x<0 || s.y<0 || s.x>=n || s.y>=n) continue;

                                     if(u[s.x][s.y]) continue;  //判断生成的新点是否合法，是否访问过，是否在棋盘内

                                     u[s.x][s.y]=1;

                                     s.stp=t.stp+1;

                                     Q.push_back(s);

                            }

                   }

Dfs深度优先搜索

重要思想是尽可能的往深处搜

int cnt=0;  //一个全局计数器

Dfs_Visit()

{

          

         for(int i=0;i

         {

                   If(!vis[i])

                            Dfs(i);

}

}

Dfs(int t)

{

         vis[t]=1;

         pre[t]=cnt++;   //记录访问到它的时间

         for(i=0;i

         {

                   If(vis[i]!=0 && graph[i][t]) //存在未访问过的边

                            Dfs(i);

}

finish[t]=cnt++;  //记录它的孩子全部被搜完的时间（结束时间）

}

Pre和finish数组记录的东西很有用~~将来讲图论的时候会仔细讲，大家先有个概念。

Dfs的在无向图一个应用就是求无向图的连通块

例如此图的连通块数就是2

例题：NEUOJ 1002

想致富，先修路，少生孩子多种树

Time Limit: 1s   Memory Limit: 30MB

Describe:

俗话说得好“想致富，先修路，少生孩子多种树”。c4pt0r的父亲是个政府官员，希望使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。最少还需要建设多少条道路？ 你能帮助他吗？

Input:

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。

Output:

对每个测试用例，在1行里输出最少还需要建设的道路数目。

Sample Input:

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

Sample Output:

1
0
2
998

此题如果我们把城市抽象成节点，道路变成边，那么我们求出连通块数后，减1便是需要添加的最少道路数（想想~~很简单）

我的代码：

#include

#include

#define G_size 100000

#define V_size 11000

typedef struct Graph

{

    int id;

    int next;

} Graph;

typedef struct Edge

{

    int s, e;

} Edge;

Edge E[G_size];

Graph GA[G_size], GT[G_size];

int N, M;

int G_end;

int order[V_size], id[V_size], vis[V_size], in[V_size];

int cnt, scnt, pos;

void Insert(int s, int e)   // 我这里的图是用邻接表表示的~~~用邻接矩阵完全可以。。。这个邻接表写得有点难懂，大家先不要看，理解思想就好，讲图论的时候会仔细解释

{

    int p;

    p = s;

    while (GA[p].next)

        p = GA[p].next;

    GA[G_end].id = e;

    GA[p].next = G_end;

    p = e;

    while (GT[p].next)

        p = GT[p].next;

    GT[G_end].id = s;

    GT[p].next = G_end;

    G_end++;

}

void DFSA(int x)

{

    int p, q;

    vis[x] = 1;

    p = GA[x].next;

    while (p)

    {

        q = GA[p].id;

        if (!vis[q])

            DFSA(q);

        p = GA[p].next;

    }

}

void Solve()  

{

    int s, e;

    int i;

    memset(GA, 0, sizeof(GA));

    memset(GT, 0, sizeof(GT));

    memset(E, 0, sizeof(E));

    G_end = N + 1;

    for (i = 0; i < M; i++)

    {

        scanf("%d %d", &s, &e);

        E[i].s = s - 1;

        E[i].e = e - 1;

        Insert(s - 1, e - 1);

        Insert(e - 1, s - 1);

    }

    memset(vis, 0, sizeof(vis));

    cnt = 0;

  

    for(i=0;i

    {

        if (!vis[ i])

        {

            DFSA(i);

            cnt++;

        }

    }

    printf("%d\n",cnt-1);

}

回溯搜索

分成子集型和排列型

子集型：对所给全集搜索出一个满足要求的子集

框架

Void backtrack(int t)

{

         if(t > n) output(x);

         else{

                            for(int i = 0; i <= 1; I ++){

                                     x[t] = i;

                                     if(constrain(t))   //约束函数，用来剪枝~~可以不写

                                                        backtrack(t + 1);

                            }

                   }

}

}

例：0/1背包的回溯解法

排列型~

•    Void backtrack(int t)

•    {

         if(t > n) output(x);

         else{

                            for(int i = t; i <= n; i ++){

                                     swap(x[t], x[i]);//用第i个元素代替第t 个元素

                                     if(constrain(t))  //同样是约束函数

                                               backtrack(t + 1);

                                     swap(x[t], x[i]);

                            }

                       }

}

例：字符串生成全排列