二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(20)

深度优先搜索

遍历方法

从图中某个顶点出发，访问此顶点，然后依次从其未被访问的邻接点出发深度优先遍历图；若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。

分析方法

方法：画一棵“深度优先搜索树”。

例：下图从A出发深度优先搜索的结果是：ABEDC。

分析：画“深度优先搜索树”。从A出发，访问A(画圈作标记)，A的邻接点有B和C(作为A的孩子)，B未访问，访问B(画圈)，B的邻接点有E(作B的孩子)，...，以此类推，画出搜索树。深度优先搜索的过程就是沿着该搜索树先根遍历的过程。

技巧：顶点的邻接点是无所谓次序的，所以同一个图的深度优先遍历序列可能不同，但在遍历时(除非邻接点的次序有明确规定)一般按照编号顺序安排邻接点的次序。

算法

课本上的算法稍加改动：

void DFSTraverse ( Graph G )

{

visited [0 .. G.vexnum-1] = false; // 初始化访问标志为未访问(false) for ( v=0; v<G.vexnum; v++ )

if ( ! visited[v] ) DFS ( G, v ); // 从未被访问的顶点开始DFS }

void DFS ( Graph G, int v )

{

visit ( v ); visited [v] = true; // 访问顶点v并作标记

for ( w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w) )

if ( ! visited[w] ) DFS ( G, w ); // 分别从每个未访问的邻接点开始DFS }

其中的FirstAdjVex(G,v)表示图G中顶点v的第一个邻接点，NextAdjVex(G,v,w)表示图G中顶点v的邻接点w之后v的下一个邻接点。

深度优先搜索算法有广泛的应用，以上算法是这些应用的基础。

广度优先搜索

遍历方法

从图中某顶点出发，访问此顶点之后依次访问其各个未被访问的邻接点，然后从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问，直至所有已被访问的顶点的邻接点都被访问。若图中尚有顶点未被访问，则另选图中未被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。 广度优先搜索从某顶点出发，要依次访问路径长度为1，2，? 的顶点。

分析方法

方法：画一棵“广度优先搜索树”。

例：下图从A出发广度优先遍历的结果是：ABCED。

分析：画“广度优先搜索树”。与深度优先搜索树类似，A为根，其邻接点为其孩子，访问一个顶点，则扩展出其孩子。不过广度优先搜索的访问次序是对该树按层遍历的结果。

算法

利用队列(类似按层遍历二叉树)。

void BFSTraverse ( Graph G )

{

visited [0 .. G.vexnum-1] = false; // 初始化访问标志为未访问(false) InitQueue ( Q );

for ( v=0; v<G.vexnum; v++ )

if ( ! visited[v] ) {

// 从v出发广度优先搜索

visit ( v ); visited [v] = true;

EnQueue ( Q, v );

while ( ! QueueEmpty(Q) ) {

DeQueue ( Q, u );

for ( w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w) )

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-20.html