深度优先遍历和广度优先遍历

首先来看一下两者之间的区别：

深度优先遍历（简称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入队

继续，以此类推，将一个节点出队，就将它周围的节点入队，直到所有的节点出队完毕，遍历完成

#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;
}

谢谢观看，如果有不足之处，敬请谅解。

文章出处登录后可见！

已经登录？立即刷新

深度优先遍历和广度优先遍历

相关推荐