1.广度优先搜索（BFS）

• 简介
  宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。（百度百科）
• 算法思路
  广度优先搜索就是以广度优先进行搜索，什么意思呢？个人理解，这是一个“扩散”的过程，就像火烧草原一样。BFS访问完一个元素后，接着会将与之相关链的元素加入队列中准备访问。
• 伪代码

  BFS（起点）{
  处理起点；
  标记起点为已处理点；
  当处理队列非空{
      弹出队头，作为现在要处理的点；
      处理现在点；
      标记为已处理；
      对所有与现在点关联的点{
          如果未处理并且符合边界条件
              加入队列；
      }
  }
  }

  2.深度优先搜索（DFS）

• 简介
  深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。（百度百科）
• 算法思路
  DFS好比走迷宫，先一直往深处走，如果到了边界就返回，直到走出迷宫。
• 伪代码

  DFS(传入点){
  处理传入点；
  标记为已处理；
  对所有与传入点相关联的点{
      如果未处理并且符合边界条件
          DFS(这个点)；
  }
  }

  3.两种算法的实现（以HDU1241为例）

• 原题
  • Problem Description
    The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
  • Input
    The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either ‘*’, representing the absence of oil, or ‘@’, representing an oil pocket.
  • Output
    For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
  • Sample Input
    1 1
    *
    3 5
    *@*@*
    **@**
    *@*@*
    1 8
    @@****@*
    5 5
    ****@
    *@@*@
    *@**@
    @@@*@
    @@**@
    0 0
  • Sample Output
    0
    1
    2
    2
• DFS代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn=105;

char map[maxn][maxn];
int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};
int m,n;
int sum;

void dfs(int x,int y)
{
    map[x][y] = '*';
    for(int i = 0;i < 8;++i)
    {
        if(map[x + dir[i][0]][y + dir[i][1]] == '@')
            dfs(x + dir[i][0],y + dir[i][1]);
    }
}

int main()
{
    while(scanf("%d %d",&m,&n) && m != 0 && n != 0)
    {
        memset(map,0,sizeof(map));
        sum = 0;
        for(int i = 1;i <= m;++i)
            scanf("%s",map[i] + 1);
        for(int i = 1;i <= m;++i)
            for(int j = 1;j <= n;++j)
            {
                if(map[i][j]=='@')
                {
                    sum++;
                    map[i][j] = '*';
                    dfs(i,j);
                }
            }
        printf("%d\n", sum);
    }
    return 0;
}

• BFS代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn=105;

char map[maxn][maxn];
int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};
int m,n;
int sum;
struct node{int x,y;} now,ne;

void bfs(int x,int y)
{
    queue <node> q;
    now.x = x;
    now.y = y;
    q.push(now);
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(int i = 0;i < 8;i++)
        {
            ne.x = now.x + dir[i][0];
            ne.y = now.y + dir[i][1];
            if(map[ne.x][ne.y] == '@')
            {
                map[ne.x][ne.y] = '*';
                q.push(ne);
            }
        }
    }
}

int main()
{
    while(scanf("%d %d",&m,&n) && m != 0 && n != 0)
    {
        memset(map,0,sizeof(map));
        sum = 0;
        for(int i = 1;i <= m;++i)
            scanf("%s",map[i] + 1);
        for(int i = 1;i <= m;++i)
            for(int j = 1;j <= n;++j)
            {
                if(map[i][j]=='@')
                {
                    sum++;
                    map[i][j] = '*';
                    // bfs(i,j);
                    dfs(i,j);
                }
            }
        printf("%d\n", sum);
    }
    return 0;
}

• 注意
  由于题目特性，本里不需要另外判断是否处理过。

总提纲：《数据结构》期末提纲小结