图的深度和广度优先算法
一.图的遍历
假设初始状态是图中所有顶点都未被访问，则深度优先搜索方法的步骤是:
1)选取图中某一顶点Vi为出发点，访问并标记该顶点;
2)以Vi为当前顶点，依次搜索Vi的每个邻接点Vj，若Vj未被访问过，则访问和标记邻接点Vj，若Vj已被访问过，则搜索Vi的下一个邻接点;
3)以Vj为当前顶点，重复步骤2)，直到图中和Vi有路径相通的顶点都被访问为止;
4)若图中尚有顶点未被访问过(非连通的情况下)，则可任取图中的一个未被访问的顶点作为出发点，重复上述过程，直至图中所有顶点都被访问。
二.广度优先搜索算法
使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。
通常用搜索技术解决的问题可以分成两类:一类问题是给定初始结点，要求找出符合约束条件的目标结点;另一类问题是给出初始结点和目标结点，找出一条从初始结点到达目标结点的路径。
常见的搜索算法有枚举法、广度优先搜索法、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、分支定界法等。这里来讨论一下广度优先搜索法。
一般来说，可以采用搜索算法解决的这类问题的特点是:
1.有一组具体的状态，状态是问题可能出现的每一种情况。全体状态所构成的状态空间是有限的，问题规模较小。
2.在问题的解答过程中，可以从一个状态按照问题给定的条件，转变为另外的一个或几个状态。
3.可以判断一个状态的合法性,并且有明确的一个或多个目标状态。 4.所要解决的问题是:根据给定的初始状态找出目标状态，或根据给定的初始状态和结束状态，找出一条从初始状态到结束状态的路径。
采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。 广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐
一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的
原则
组织架构调整原则组织架构设计原则组织架构设置原则财政预算编制原则问卷调查设计原则
是先生成的结点先扩展。
广度优先搜索算法中，为了便于进行搜索，要设置一个表存储所有的结点，为了满足先生成的结点先扩展的原则，存储结点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出结点进行扩展。对生成的新结点，要检查它是否已在队列中存在，还要检查它是否目标结点。如果新结点是目标结点，则搜索成功，程序结束;若新结点不是目标结点，并且未曾在队列中出现过，则将它加入到队列尾，否则将它丢弃，再从队列头取出结点进行扩展......。最终可能产生两种结果:找到目标结点，或扩展完所有结点而没有找到目标结点。 如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。
对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同，对具体的问题需要进行具体分析。
广度优先搜索算法的算法框架
Private Type TNode '定义一个结点数据类型
.... '根据具体问题确定所需的数据类型
End Type
Dim State() As TNode '定义TNode类型的数组，作为存储结点的队列
Private Sub BFS() 'BFS算法主程序
Dim Temp As TNode 'TNode型临时结点
Dim Head As Integer,Tail As Integer '队列头指针和尾指针
ReDim State(0)
InputData '从文件中读入数据进行初始化
Head=0
Tail=0 ' 队列头指针和尾指针都指向队列头
Do While Head<=Tail '队列非空时循环
'根据具体问题确定一个结点怎样扩展
Temp= State(0) '取队列头的结点
If Extend Then '如果该结点可以扩展则产生一个新结点
If Not Repeat Then '如果新结点未曾在队列中出现过
Tail=Tail+1 ' 将新结点加入队列尾
ReDim Preserve State(Tail)
State(Tail) =Temp
State(Tail) .Sire=Head '
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
父结点标识
If Found Then ' 如果新结点是目标结点
Tail=Tail+1 ' 将队列尾结点的父结点指针指向队列尾
ReDim Preserve State(Tail)
State(Tail) =Tail-1
PrintPath '输出路径
Exit Sub '退出程序
End If
End If
End If
Head=Head+1 '队列头的结点扩展完后出队，取下一结点扩展
Loop
End Sub
其中的
InputData是从文件中读入初始化的数据，对问题的初始状态等进行设置的子过程
Extend是判断结点是否能扩展的子过程，如果能则产生新结点 Repeat是检查新结点是否在队列中已经出现的函数，返回一个布尔值 Find则是检查新结点是否目标结点的函数，也返回一个布尔值 这些过程和函数要根据具体问题进行编写。另外，PrintPath用递归方式输出路径的子过程:
Private Sub PrintPath(State() As Node,ByVal k As Integer)
If k>0 Then
k=State(k).Sire
PrintPath State,k
OutState State(k)
End If
End Sub
因为当搜索到目标结点时，该结点记录的是其父结点的标识，所以需要再将队列尾指针前移，将其父结点指向当前的队尾，也即搜索到的目标结点。另外得到的路径是从队列尾回到队列头的逆向路径，输出时要逆转，所以采用递归方式，可以自动输出正向路径。子过程OutState与具体的问题有关，要视需要输出的结点信息而定。
这里将整个求解问题的过程分成了多个子过程，对不同的问题，程序的框架是不变的，只需根据实际情况编写子过程的代码即可。
下面的例子中，虽然某些子过程只有一条语句，为与算法框架一致，仍使用单独的子过程表示。
图的广度优先算法的实现
#include
using namespace std;
const int N=11;
struct node
{
int front;
int dis;
}front_point[N];//记录每个点到起点的距离和每个点的前驱 int graph[N][N];//用邻接矩阵来表示图
bool visited[N];//记录点是否被标记
void BFS(int x,int k)//广搜
{
int i;
bool flag=false;
for(i=0;i>x>>y)//输入图
{
graph[x-1][y-1]=graph[y-1][x-1]=1;
}
for(i=0;i
本文档为【图的深度和广度优先算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483