首先来看一下两者之间的区别：
深度优先遍历（简称DFS）：就是先选择一条路尽可能深入，走到头（即该点没有未被访问过的相邻节点）再回退到上一个节点，继续探索该节点的其他支路，就该支路继续深入的遍历方法
以示例作参考
先选择一条作为深度优先遍历首次探索到的支路
探索到6节点，发现6节点周围没有未被探索到的节点，回退到5节点
5节点周围也没有未被探索到的节点，回退到3节点
此时，3节点周围的4节点未被访问，探索4节点
探索到4节点后，发现4节点周围也没有未被访问过的节点，继续回退到3节点
此时，发现3节点周围也没有未被访问过的节点，继续回退到0节点
回退到0节点后，发现2节点未被访问过，继续探索2节点的支路，以此类推，直到所有结点都被访问过完毕
来看一下代码怎么写
由以上示例得知，实现深度优先遍历的关键在于回溯 ，自后向前，追溯曾经走过的路径。想实现回溯，我们可以利用栈的先进后出的特性，也可以采用递归的方式。
首先将节点0，3，5，6入栈，此时栈顶是6
从节点6退回到节点5，节点6出栈，此时栈顶是5
从节点5退回到节点3，节点5出栈，栈顶变为3，节点3周围有节点4未被访问，节点4入栈
从节点4与退回到节点3，节点4出栈，
从节点3回退到节点0，3出栈，依次类推，实现回溯，最终遍历完所有顶点。
其实，我们学习过的前序遍历，后序遍历中序遍历的思想与DFS的思想是类似的。
#include<stdio.h>
#include<stack>
#define MAX 100
using namespace std;
typedef struct
{
int e[MAX][MAX];
int ves;
int edge;
int book[MAX];//标志判断是否有被访问过
}MGraph;
void createMGraph(MGraph *G)
{
int i;
int j;
int start;
int end;
printf("please input the ves and edge:\n");
scanf("%d %d",&G->ves,&G->edge);
//初始化
for(i = 0; i < G->ves; i++)
{
for(j = 0; j < G->ves; j++)
G->e[i][j] = 0;
G->book[i] = 0;//没被访问过的结点置为0
}
//创建邻接矩阵
printf("please input the (vi,vj)\n");
for(i = 0; i < G->edge; i++)
{
scanf("%d %d",&start,&end);
G->e[start][end] = 1;
}
}
void dfs(MGraph* G,int ves)
{
stack<int> s;//创建一个栈
printf("%d ", ves);
G->book[ves] = 1;//已经访问过结点ves了
s.push(ves);//入栈
while(!s.empty())
{
int data, i;
data = s.top();//取top的顶点
for(i = 0; i < G->ves; i++)
{
if(G->e[data][i] != 0 && G->book[i] != 1)
{
printf("%d ", i);
G->book[i] = 1;
s.push(i);
break;// 开始遍历下一个点的邻接矩阵表
}
}
if(i == G->ves)//data相邻的结点都访问结束了，就弹出data
{
s.pop();
}
}
}
int main()
{
MGraph G;
createMGraph(&G);
dfs(&G,0);
return 0;
}
广度优先遍历（简称BFS）：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。是由内到外的，层层递进的一种遍历方法。
示例：
我们以节点0为起始节点
然后，我们再探索与节点0相邻的节点1，7，2，3
接着，我们探索与节点0相隔了一层的节点8，4，5
然后，再次探索，与节点0相隔了两层的节点6
至此，所有节点探索完毕。
来看一下代码怎么写
由以上示例得知，实现深度优先遍历的关键在于重放，按照广度优先遍历的思想，我们首先遍历顶点0，然后接着遍历顶点1，7，2，3，接下来我们要遍历更外围的顶点，可是如何找到这些更外围的顶点呢？我们需要把刚才遍历过的顶点1、2、3、7按顺序重新回顾一遍，从顶点1发现邻近的顶点8；从顶点3发现邻近的顶点4、5。
首先将节点0入队
接下来顶点0出队，遍历顶点0的邻近顶点1，7，2，3，并且把它们入队：
然后节点1出队，遍历节点1附件的节点8，节点8入队
接下来节点7出队，遍历节点7周围节点，发现无节点入队，则继续节点2出队，遍历节点2周围节点，发现无节点入队，继续向后出队
然后节点3出队，遍历节点1附件的节点4，5，节点4，5入队
继续，以此类推，将一个节点出队，就将它周围的节点入队，直到所有的节点出队完毕，遍历完成文章来源：https://www.toymoban.com/news/detail-753426.html
#include<iostream>
using namespace std;
const int n = 11;//结点个数
const int SIZE = 10;
class queue
{
private:
int buffer[SIZE];
int rear, head;//rear指向队尾元素，front指向队列前一格
int update(int value) { return (value + 1) % SIZE; }
public:
queue():head(0),rear(0){}
bool queueNull() { return rear == head;}//队空队尾下标和队首下标相同
bool queueMax() { return update(rear) == head; } //队满
bool queueAdd(int E)
{
if (queueMax()) return false;
rear = update(rear);
buffer[rear] = E;
return true;
}
bool getFirstQueue(int& E)
{
if (queueNull()) return false;
head = update(head);
E = buffer[head];
return true;
}
};
bool flag[n];
void BreadthFirstSearch(int begin)
{
for (int i = 0; i < n; i++) flag[i] = false;
queue que;//创建队列对象
que.queueAdd(begin);
flag[begin] = true;
int node;
while (!que.queueNull())
{
que.getFirstQueue(node);
cout << node << ",";
for (int i=0;i<n;i++)
{
if (nextClose[node][i] && !flag[i])
{
que.queueAdd(i);
flag[i] = true;
}
}
}
}
int main()
{
const bool F=false,T=ture;
int n;
bool nextClose[100][100];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
{
bool b;
cin>>b;
nextClose[i][j]=b;
}
}
BreadthFirstSearch(0);
cout << "Hello World" << endl;
}谢谢观看，如果有不足之处，敬请谅解。文章来源地址https://www.toymoban.com/news/detail-753426.html
到了这里，关于深度优先遍历和广度优先遍历的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
