备战蓝桥杯决赛----坚持第三天！！！

                        “在某一事件段，你突然需要有几件重要的事情需要处理。”       

                                                                                                              ------今天晚上的我

      就算是今晚很忙，也要想到自己的坚持计划，要做一个有“原则”的程序猿（感觉自己离正常人类越来越远）。

      相比前两天来说，今天要说的内容感觉非常简单。我是从时间上得出的结论，之前都是两个知识点看一整天，今天这两个知识点，顶多也就一小时~~~当然绝对不会是很简单的那种。

      接下来正式介绍，今天所学习的算法知识点：深度优先遍历（DFS）与广度优先遍历（BFS）。

      为什么说这两个知识点简单呢，是因为自己翻了很久找到的一遍写的比较好的博客，附上博客链接，希望大家可以先阅读此篇博客：https://blog.csdn.net/wizard_wsq/article/details/50628009

      接下来对上边博客内程序，进行一些代码注释（上边博主的程序已经写的非常精练了，仅仅做些注释，方便理解）

BFS：

#include <iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
    { 0, 1, 1, 0, 0 },
    { 0, 0, 1, 1, 0 },
    { 0, 1, 1, 1, 0 },
    { 1, 0, 0, 0, 0 },
    { 0, 0, 1, 1, 0 }
};
int visited[N + 1] = { 0};
void BFS(int start)
{
   queue<int> q; //定义一个队列 
   q.push(start); //开始点入队 
   while(!q.empty()){   //队列不为空，执行广搜 
   	int front = q.front();   
    cout<<front<<" ";
   	q.pop();
   	for(int i=0;i<N;i++){    //这里for循环的范围与上面博客中的不同，是想保持与邻接矩阵点相一致
   	   if(!visited[front]&&maze[front-1][i]==1){  //查询是否存在与节点front相连的未访问节点 
   	   	      visited[front]=1;
   	   	      q.push(front);
		  }	
	   }
   	
   } 
}
int main()
{
    for (int i = 1; i <= N; i++)  //这里的for是为了避免开始节点到某节点不可达而访问不到的情况，通过for循环遍历循环所有节点 
    {
        if (visited[i] == 1)
            continue;
        BFS(i);
    }
    return 0;
}

DFS：

#include <iostream>
#define N 5
using namespace std;
int maze[N][N] = {
    { 0, 1, 1, 0, 0 },
    { 0, 0, 1, 0, 1 },
    { 0, 0, 1, 0, 0 },
    { 1, 1, 0, 0, 1 },
    { 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
    visited[start] = 1;
    for (int i = 0; i < N; i++)
    {
        if (!visited[i] && maze[start - 1][i] == 1)
            DFS(i); //递归方式的深度优先遍历 
    }
    cout << start << " ";
}
int main()
{
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] == 1)
            continue;
        DFS(i);
    }
    return 0;
}

对于普通的DFS，由于递归会占用很多时间，所以这里使用栈进行优化

#include <iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
    { 0, 1, 1, 0, 0 },
    { 0, 0, 1, 0, 1 },
    { 0, 0, 1, 0, 0 },
    { 1, 1, 0, 0, 1 },
    { 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
    stack<int> s;
    s.push(start);
    visited[start] = 1;
    bool is_push = false;
    while (!s.empty())
    {
        is_push = false; //标志位，判断某节点是否访问到了一个未访问的相连节点
        int v = s.top();
        for (int i = 0; i <= N; i++)
        {
            if (maze[v - 1][i] == 1 && !visited[i])
            {
                visited[i] = 1;
                s.push(i);
                is_push = true;
                break;  //找到下一个节点，结束循环，再以此节点进行寻找相连节点（实现深度优先遍历）
            }
        }
        if (!is_push)  //若没有访问到相连节点，做弹出操作（相当于递归DFS中的返回上一层）
        {
            cout << v << " ";
            s.pop();
        }

    }
}
int main()
{
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] == 1)
            continue;
        DFS(i);
    }
    return 0;
}

   实在坚持不住了，洗洗睡了，明天找些相关题目，加强一下应用能力。又成功坚（fu）持（yan）了一天~~~~