图的搜索算法第1页，共39页，星期日，2025年，2月5日图的邻接表表示对图（有向或无向）G=V,E（为方便记，假定V={1,2,…,n}），其邻接表表示是一个由|V|个链表组成数组，对每个u?V，链表Adj[u]称为对应顶点u的邻接表。它包含G中所有与u相邻的顶点。每个邻接表中顶点通常是按任意顺序存放的。第2页，共39页，星期日，2025年，2月5日6.1广度优先搜索1．问题的理解与描述给定一个图（有向或无向）G=V,E和其中的一个源顶点s，广度优先搜索系统地探索G的边以“发现”从s出发每一个可达的顶点：发现从s出发距离为k+1的顶点之前先发现距离为k的顶点。搜索所经路径中的顶点，按先后顺序构成“父子关系”：先发现的顶点u，并由u出发发现与其相邻的顶点v，则称u为v的父亲。由于每个顶点只有最多一个顶点作为它的父亲，所以搜索路径必构成一棵根树（树根为起始顶点s）G?。我们把这棵树称为G的广度优先树。与此同时，我们还计算出了从s到这些可达顶点的距离（最少的边数即“最短路径”）。这样，图的广度搜索问题形式化表述如下。输入：图G=V,E，源顶点s?V。输出：G的广度优先树G?以及树中从树根s（源顶点）到各节点的距离。第3页，共39页，星期日，2025年，2月5日对一个无向图的BFS操作第4页，共39页，星期日，2025年，2月5日2．算法的伪代码描述BFS(G,s)1for每个顶点u?V[G]-{s}2docolor[u]←WHITE3d[u]←?4 ?[u]←NIL5color[s]←GRAY6d[s]←07Q←?8ENQUEUE(Q,s)9whileQ≠?10dou←DEQUEUE(Q)11foreachv?Adj[u]12doifcolor[v]=WHITE13thencolor[v]←GRAY14 ?[v]←u15d[v]←d[u]+116ENQUEUE(Q,v)17 color[u]←BLACK18return?andd第5页，共39页，星期日，2025年，2月5日3．算法的正确性引理6-1从源顶点s到任何顶点v的距离必不超过运行BFS后过此顶点的d属性。引理6-2设队列Q={v1,v2,…,vr}。则d[vr]?d[v1]+1（即对尾元素的d属性不超过队首元素的d属性加1），且d[v1]?d[v2]?...?d[vr]。定理6-3运行BFS后，图G中各顶点v的d属性记录了s到v的距离。第6页，共39页，星期日，2025年，2月5日4．算法的运行时间第1～4行的循环重复|V|次。另一方面，由于每条边在搜索过程中有且仅有一次被访问，第9～17行两重循环嵌套内的操作被执行|E|次。所以BFS的总运行时间是Θ(V+E)。于是，广度优先搜索运行于G的邻接表示规模的线性时间内。第7页，共39页，星期日，2025年，2月5日6.2深度优先搜索深度优先搜索（DepthFirstSearch，DFS）所遵循的策略，如同其名称所云，是在图中尽可能“更深”地进行搜索。在深度优先搜索中，对最新发现的顶点v若此顶点尚有未探索过从其出发的边就探索之。当v的所有边都被探索过，搜索“回溯”到从其出发发现顶点v的顶点。此过程继续直至发现所有从源点可达的顶点。若图中还有未发现的顶点，则以其中之一为新的源点重复搜索，直至所有的顶点都被发现。与BFS中源顶点是指定的稍有不同。DFS搜索轨迹G?将形成一片森林——深度优先森林第8页，共39页，星期日，2025年，2月5日1．问题的理解与描述在深度优先搜索过程中对每一个顶点u跟踪两个时间：发现时间d[u]和完成时间f[u]。d[u]记录首次发现（u由白色变成灰色）时刻，f[u]记录完成v的邻接表检测（变成黑色）时刻。输入：图G=V,E。输出：G的深度优先森林G?以及图中各顶点在搜索过程中的发现时间和完成时间。第9页，共39页，星期日，2025年，2月5日2．算法的伪代码描述DFS(G)1foreachvertexu?V[G]2docolor[u]←WHITE3?[u]←NIL4time←05S←?6foreachvertex