深度优先搜索的基本思路是：按照某种条件一个劲儿的往下搜索，一旦遇到不符合条件的情况或者是走到尽头了就退回到上一步，然后选择另外一个路径继续搜索……如此循环往复，直到把所有符合条件的点遍历完毕为止。简单来说，大致符合下面这张图片所示的遍历步骤（步骤6之后的步骤没有画）
那具体实现是怎么实现的呢？我们以下面这个图为例，感受一下用深度优先搜索遍历图的过程。
1.首先，你需要定义一个栈（真正编程实现的时候不一定用stack，用vector也行，只要能模拟出栈的功能即可）。我们执行的过程大体是这样的，当前栈顶元素即为被访问的结点，该结点随即出站，然后与该结点相邻的结点进栈，不停的执行该过程，直到所有元素都被访问过了为止，而此时，栈为空。 2.我们从1结点开始遍历，所以最开始的时候结点1先入栈。此时栈中的元素为：1 3.1结点被访问过了，随即与1相邻的结点，即2和5进栈，所以此时栈中的元素分别为：2、 5 4.栈顶元素为5，所以此时代表正在你访问5。5随即出栈，与5结点相邻的结点为8，9，6和2，但是2现在已经在栈里面了，所以不用再次入栈，此时栈中的元素分别为：2,5,8,9,6。 5.栈顶元素此时为6，即正在访问6，6随即出栈，与6相邻的结点为2,7,9。但此时2,9已经在栈中了，不必再次入栈，所以只需让7入栈，此时栈中的元素由底向上为：2,5,8,9,7。 6.此时，栈顶元素为7，即7被访问过了，7随即出栈，与7相邻的结点为3,4和10，这些结点此时既没有被访问过也没有已存在于栈中，所以一次进栈，那么此时栈中的元素为：2,5,8,9,3,4,10。 7.栈顶元素为10，代表此时已访问10, 10随即出栈，与10相邻的结点为7,9。7已经被访问过，不必入栈。9已经在栈中，也不必入栈。此时栈中的元素为：2,5,8,9,3,4。 8.栈顶元素为4，代表4已经被访问，4出栈。与4相邻的结点为3和7。3已经在栈中，7被访问过了，所以都不用入栈。此时栈中的元素：2,5,8,9,3。 9.栈顶元素为3，代表正在访问3。3出栈，与3相邻的元素为2,7 。2已经在栈中，7被访问过了。所以都不用入栈。此时栈中元素为：2,5,8,9。 10.栈顶元素为9。代表正在访问9结点。9出栈，与9相邻的结点为8,5,6 。其中5,8已经在栈中了，6已经被访问过。所以，都不必入栈。此时栈中的元素为：2,5,8 。 11.栈顶元素为8，代表正在访问8结点。8出栈，与8相邻的的元素为5和9，其中5在栈中，9已经被访问过了，所以都不用入栈，此时栈中的结点为2,5 。 12.栈顶元素为5，代表正在访问5结点。5出栈，与5相邻的的元素为1,2和6，其中1,2,6已经被访问过了，所以都不用入栈，此时栈中的结点为2 。 13.只剩下一个2了，2相邻的结点已全部被访问过了，所以直接出栈即可。此时栈空，深度优先搜索结束。 以下这张图片显示了上述过程的路径： 二、广度优先搜索 与深度优先搜索不同的是，广度优先搜索使用的是队列（深度优先搜索使用的是栈） 广度优先搜索的思路是：每次访问队头的结点，访问过了，即出队列，然后与该结点相邻的结点加入队列，依次类推，直到队列为空为止。它的过程类似于下面这个图片所示的样式： 我们还以下面这个图为例： 1.首先我们得先申请一个空队列。 2.我们还是将1结点作为遍历的开始。因此1先入队列。此时队列元素为：1。 3.队头为1，表明正在访问1结点，1出队。与1结点相邻的结点2和5分别入队，此时队列元素为：2,5 。 4.队头为2，表明正在访问2结点，2出队，与2结点相邻的结点5,3,6，5已经在队列中了，无需再次入队。于是，3,6入队。此时队列元素为：5,3,6。 5.队头为5，表明正在访问5结点，5出队。与5相邻的结点为6,8和9，其中6已经在队列中，所以8，9入队，此时队列元素为：3,6,8,9 。 6.队头为3，表明正在访问3，3出队。与3相邻的结点4和7入队，此时队列元素为：6,8,9,4,7 。 7.队头为6，表明正在访问6，6出队。与6相邻的结点7和9已经在队列中，无需再次入队。此时队列元素为：8,9,4,7 。 8.队头为8，表明正在访问8，8出队。与8相邻的结点5已经遍历过，9已经在队列中，所以都不用入队了，此时队列元素为：9,4,7。 9.队头元素为9，表明正在访问9，9出队。与9相邻的结点6已经遍历过了，所以只需让10入队，此时队列元素为：4,7,10 。 10.队头元素为4，表明正在访问4，4出队。与4相邻的结点3已经遍历过，7已经在队列中，无需处理。此时队列元素：7,10 。 11.队头元素为7，表明正在访问7，7出队。与其相邻的结点3,4和10都无需入队，此时队列元素为：10 。 12.队列当中只剩下10了，语气相邻的元素9和7都已经遍历过，所以直接出队。 13.此时队列为空，遍历结束。 遍历顺序如下图所示： 例子：在我们使用windows操作系统自带的画图软件的时候。当我们画一个封闭的图形，然后用油漆桶工具点击一下，整个封闭图形的内部就会被填充上颜色。颜色被填充的这个过程就可以理解为是搜索算法实现的。我们知道屏幕是有许许多多的像素点的。我们遍历封闭图形之内的像素点，直到把封闭图形之内所有的像素点都遍历完毕，就把这块区域的颜色给填充上了。我们现在就在控制台上简单的模拟一下这个过程。 我们先定义一个一个二维数组： int a[10][10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 其中1，代表边界。0代表没有染色的像素点，我们在1的内部一点作为起点。看看能不能把由1围城的封闭区域全部给填充为1.我们都从（3,3）这个点开始遍历。
首先，我们用深度优先搜索，深度优先搜索的实现又分为两种方法：递归与非递归的方式。
1.
1.递归的方式：
#include<iostream> #include<stack> #include<windows.h> using namespace std; int a[10][10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; void show() { for(int i=0;i<10;i++) { for(int j=0;j<10;j++) { if(1==a[i][j]) { cout<<"* "; } else { cout<<" "; } } cout<<endl; } } void DFS(int x,int y) { Sleep(1000); system("cls"); show();///这几行代码可以使你看到遍历的过程 if(a[x][y]==1) { return; } else { a[x][y] = 1; } int tmpX = x; int tmpY = y; ///向上搜索 tmpY--; if(a[tmpX][tmpY]==0) { DFS(tmpX,tmpY); } else { tmpY++; } ///向下搜索 tmpY++; if(a[tmpX][tmpY]==0) { DFS(tmpX,tmpY); } else { tmpY--; } ///向左搜索 tmpX--; if(a[tmpX][tmpY]==0) { DFS(tmpX,tmpY); } else { tmpX++; } ///向右搜索 tmpX++; if(a[tmpX][tmpY]==0) { DFS(tmpX,tmpY); } else { tmpX--; } } int main() { show(); DFS(3,3); return 0; } 2.非递归的方式： /* 由前面所讲的过程知道入栈的时候需要遍历栈 看是否已经存在于栈中，但是栈貌似无法遍历， 所以我们用vector来模拟栈。 */ #include<iostream> #include<vector> #include<Windows.h> using namespace std; int a[10][10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; void show() { for (int i = 0; i<10; i++) { for (int j = 0; j<10; j++) { if (1 == a[i][j]) { cout << "* "; } else { cout << " "; } } cout << endl; } } struct Point { Point(int m_x, int m_y) { x = m_x; y = m_y; } int x; int y; }; int main() { vector<Point> p; p.push_back(Point(3, 3));///先把第一个要遍历的点压入栈。 int tmpX, tmpY; bool visit; while (p.size() != 0) { auto pos = p.back();///vector的尾部，相当于栈顶 p.pop_back();///出栈 a[pos.x][pos.y] = 1; ///访问过的点打上标记 ///向上搜索 tmpX = pos.x; tmpY = pos.y-1; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } ///向下搜索 tmpX = pos.x; tmpY = pos.y+1; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) ///遍历栈，看当前结点是否在栈中 { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } ///向左搜索 tmpX = pos.x - 1; tmpY = pos.y; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } ///向右搜索 tmpX = pos.x+1; tmpY = pos.y; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } //显示 Sleep(1000); system("cls"); show(); } show(); system("pause"); return 0; }广度优先搜索：
//我用的是deque来实现的，因为queue遍历起来貌似有点儿难。 #include<iostream> #include<deque> #include<Windows.h> using namespace std; int a[10][10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; void show() { for (int i = 0; i<10; i++) { for (int j = 0; j<10; j++) { if (1 == a[i][j]) { cout << "* "; } else { cout << " "; } } cout << endl; } } struct Point { Point(int m_x, int m_y) { x = m_x; y = m_y; } int x; int y; }; int main() { deque<Point> p; p.push_back(Point(3, 3)); int tmpX, tmpY; bool visit; while (!p.empty()) { auto pos = p.front(); p.pop_front(); a[pos.x][pos.y] = 1; //向上搜 tmpX = pos.x; tmpY = pos.y - 1; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } //向下搜 tmpX = pos.x; tmpY = pos.y + 1; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } //向左搜 tmpX = pos.x - 1; tmpY = pos.y; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } //向右搜 tmpX = pos.x + 1; tmpY = pos.y; visit = false; for (auto i : p) { if (i.x == tmpX&&i.y == tmpY) { visit = true; break; } } if (visit == false && a[tmpX][tmpY] == 0) { p.push_back(Point(tmpX, tmpY)); } //显示 Sleep(1000); system("cls"); show(); } //show(); system("pause"); return 0; }