第5章 图的搜索算法.ppt

第5章 图的搜索算法
第1页，共137页，编辑于2022年，星期日
图搜索概述
第2页，共137页，编辑于2022年，星期日
1．显式图与隐式图
在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题 其中，Wij表示边上的权值，∞表示一个计算机允许的，大于所有边上权值的数；
1）邻接矩阵法
第11页，共137页，编辑于2022年，星期日
第12页，共137页，编辑于2022年，星期日
2）邻接表
对于图G中的每个结点Vi, 把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表。
邻接表由边表和顶点表两部分组成。

    无向图：Vi的邻接表中每个表结点都对应于与Vi相关联的一条边，
有向图：Vi的邻接表中每个表结点对应于Vi为始点射出的一条边。
第13页，共137页，编辑于2022年，星期日
边表为一个单链表，每个表结点均有两个域：
①邻接点域adjvex：存放与vi相邻接的顶点vj的序号j。
②链域next：将邻接表的所有表结点链在一起。
顶点表为一数组，每个元素均有两个域：
①顶点域vertex：存放顶点vi的信息
②指针域firstedge：vi的边表的头指针。
第14页，共137页，编辑于2022年，星期日
二、图搜索及其术语
1．穷举搜索与启发式搜索
穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。
启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。
第15页，共137页，编辑于2022年，星期日
2．相关概念和术语
问题状态:树中的每一个结点确定所求解问题的一个问题状态。
状态空间:由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。
解状态:是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。
答案状态:是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解
状态空间树:解空间的树结构又称隐式图。
第16页，共137页，编辑于2022年，星期日
活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。
E-结点：当前正在生成其儿子结点的活结点叫E-结点（正扩展的结点）。
死结点 ：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点 。
第17页，共137页，编辑于2022年，星期日
广度优先搜索
从图中任选一顶点V为起点，首先访问V的所有邻接点W1, W2,…, Wt,然后再依次访问W1, W2,…, Wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和起点V有路径相通的顶点均已被访问为止。
第18页，共137页，编辑于2022年，星期日
一、算法框架
1．算法的基本思路
算法设计的基本步骤为：
1）确定图的存储方式； 
2）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；
3）输出问题的结论。
第19页，共137页，编辑于2022年，星期日
2．算法框架
1、通过E-结点扩展出的活结点
2、活结点的扩展是按先来先处理的原则进行的
抽象地定义：
queue为队列类型，
InitQueue( ) ：队列初始化函数，
EnQueue(Q，k)：入队函数，QueueEmpty(Q) ：判断队空函数，
DeQueue(Q) ：出队函数。
visited[]：记录结点的搜索情况。
第20页，共137页，编辑于2022年，星期日
1）邻接表表示图的广度优先搜索算法
int visited[n]; //n 为结点个数
bfs(int k,graph head[]){ int i； queue Q ； edgenode *p； //定义队列    InitQueue(Q)； //队列初始化    print(“visit vertex”，k)； // 访问源点vk    visited[k]=1；     EnQueue(Q，k)； //vk已访问，将其入队    while(