广度遍历算法

① 无向有权的图的深度、广度优先遍历怎么做的啊，他的遍历序列怎么求呢

总结深度优先与广度优先的区别
1、区别

1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

3）深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

② 试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

从1开始，1连接7,7连接3，3连接4,4连接5,5连接6,6连接2（1已经连过了）（2连接了3,7，但是3和7都已经连过，所以回到上一级6,6的连接是1,2都已经连过，所以再回到上一级5）5连接10 。

（10连接1,6都已经连过了，所以回到上一级5，但是5的所有连接点都连过了，所以回到上一级4）4连接9,（9连接5,10都已经连过了，所以回到上一级4,4也已经练完了，所以再回到上一级3）3连接8，至此连完。

广度遍历：从1开始，连接7和9，下一个是7，连接3和10 ，下一个是9，连接5，下一个是3，连接4和8，下一个是10 连接6，下一个是5，没有什么连接的，下一个是4，没有什么连接的，下一个是8，没有什么连接的，下一个是6，连接2，至此连完。

(2)广度遍历算法扩展阅读：

通用定义：

若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。

（1）若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。

（2）若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。

（3）若G是非连通的无向图，则要若干次从外部调用DFS(或BFS)算法，才能完成对G的遍历。每一次外部调用，只能访问到G的一个连通分量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。

G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。

（4）若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。