文档介绍：图及搜索算法王璐中原工学院计算机学院 2010-4 图的基本概念?显式图?图的结构是显式给出的,包括顶点、边及权重?常用术语?环?简单图?顶点的度?终端顶点?路径与路长?连通图?网络图的基本概念?隐式图?有一些求解、最优化或证明类问题,一般仅给出初始节点和想要达到的目标,解决过程是通过在某个可能的解空间内寻找所要的解或最优解。问题的解空间多是树形或图形结构,但并没有显式给出,称为隐式图。?例: ?子集树: 0-1 背包问题,八皇后问题?排列树:旅行商问题图的存储?显式图?邻接矩阵?邻接表?隐式图?隐式图是在一定规律下构造的,一般不需要专门的存储,而是搜索中根据隐式图的规律特点确定搜索过程。宽度(广度)优先搜索?逐层搜索?首先访问出发点 v,接着依次访问 v的所有邻接点 w1,w2, …,wt ,然后再依次访问与 w1,w2, …,wt 邻接的所有未曾访问过的顶点。依此类推,直至图中所有和起点 v有路径相通的顶点都已访问为止。此时从 v开始的搜索过程结束。?若G是连通图,则一次就能搜索完所有节点;否则,在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程,直至 G中所有顶点均已被访问为止。 BFS 的基本思路及步骤?主要用于解决在显式图中寻找某一方案的问题,解决问题的方法就是通过搜索图的过程中进行相应的操作,从而解决问题。?基本步骤?确定图的存储方式?设计图搜索过程中的操作,其中包括为输出问题解而进行的存储操作。?输出问题的结论 BFS 的实现?活节点(待扩展节点)队列?初始时,活节点队列为空,根节点 A是当前扩展节点。扩展出的儿子节点,按先后顺序依次加入活节点队列, 并舍弃当前扩展节点 A。?每一个活节点只有一次机会成为扩展节点。活节点一旦成为扩展节点,就一次性产生其所有儿子节点。在这些儿子中,导致不可行解或导致非最优解的儿子被舍弃,其余儿子被加入活节点队列中。此后,从队列中取对首节点成为当前扩展节点,并重复上述节点扩展过程。?该过程一直持续到找到所需的解或活节点队列为空时为止。 BFS 实现中的注意事项?由于 BFS 一般需要在搜索结束(或到达目标)后,即搜索完所有层所有节点(队列为空时结束),才能得出问题的解。这样, 在搜索过程中,有一个重要操作就是记录当前找到的解决问题的方案。?在宽度优先扩展节点时,一个节点可能多次作为扩展对象,这是需要避免的。一般开辟数组 visited 记录图中节点被搜索的情况。 BFS 队列的实现?线性表?队列操作?InitQueue () 队列初始化?EnQueue(Q,k ) 入队?QueueEmpty(Q ) 判断队列是否为空?DeQueue(Q ) 出队?数组?进队操作:向后移动对尾下标 qe ?出队操作:向后移动对首下标 qh ?判空: qe==qh布线问题?问题描述?印刷电路板将布线区域划分为 n×m个方格阵列,如图所示。?精确的电路板布线问题要求确定连接方格 a的中点到方格 b的中点的最短布线方案。?布线时电路只能沿直线或直角布线。?为避免线路相交,已布线方格做上封闭标记,其他线路布线不允许穿过封闭区域。?为讨论方便,我们假定电路板外面的区域为已加封闭标记的方格。