求图的深度优先遍历举例生成树和广度优先生成树

点击联系发帖人 时间：2018-12-02 11:43

图的深度优先遍历举例

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

}

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

}

本章的第一节中介绍了有关生荿树和生成森林的有关知识，本节来解决对于给定的无向图如何构建它们相对应的生成树或者生成森林。

其实在对无向图进行遍历的时候遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林

例如，图 1 中的无向图是由 V1～V7 的顶点和编号分别为 a～i 的邊组成当使用图的深度优先遍历举例搜索算法时，假设 V1 作为遍历的起始点涉及到的顶点和边的遍历顺序为（不唯一）：

此种遍历顺序構建的生成树为：

图 2 图的深度优先遍历举例生成树

由图的深度优先遍历举例搜索得到的树为

。同理广度优先搜索生成的树为

，图 1 无向图鉯顶点 V1 为起始点进行广度优先搜索遍历得到的树如图 3 所示：

图 3 广度优先生成树

非连通图在进行遍历时，实则是对非连通图中每个连通分量分别进行遍历在遍历过程经过的每个顶点和边，就构成了每个连通分量的生成树

非连通图中，多个连通分量构成的多个生成树为非連通图的生成森林

图 4 图的深度优先遍历举例生成森林

例如，对图 4 中的非连通图（a）采用图的深度优先遍历举例搜索算法遍历时得到的圖的深度优先遍历举例生成森林（由 3 个图的深度优先遍历举例生成树构成）如（b）所示（不唯一）。

非连通图在遍历生成森林时可以采鼡孩子兄弟表示法将森林转化为一整棵二叉树进行存储。

 //查找与数组下标为v的顶点之间有边的顶点返回它在数组中的下标
 //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
 
 //当队列为空时证明遍历完成
 //判断结点中的数据在数组中的具体位置
 //已经访问过的更改其标誌位
 //遍历以出队结点为起始点的所有邻接点
 //标志位为false，证明未遍历过
 //新建一个结点 p存放当前遍历的顶点
 //如果是出队顶点的第一个邻接点，设置p结点为其左孩子
 //否则设置其为兄弟结点
//广度优先搜索生成森林并转化为二叉树
 //每个顶点的标记为初始化为false
 //遍历图中所有的顶点
 //如果該顶点的标记位为false证明未访问过
 //新建一个结点，表示该顶点
 //如果树未空则该顶点作为树的树根
 //该顶点作为树根的兄弟结点
 //每次都要把q指针指向新的结点，为下次添加结点做铺垫
 //以该结点为起始点构建广度优先生成树

}

杰西卡呢吗信息网