2019-11-19 12:44:08 新疆公务员考试网 //xj.huatu.com/ 文章来源:未知
如果使用的是邻接表存储结构,其DFSTraverse函数的代码几乎是相同的,只是在递归函数中因为将数组换成了链表而有不同,代码如下。
对比两个不同的存储结构的深度优先遍历算法,对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找某个顶点的邻接点需要访问矩阵中的所有元素,因为需要O(n2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。
2.2 广度优先遍历
广度优先遍历,又称为广度优先搜索,简称BFS。图的广度优先遍历就类似于树的层序遍历了。
邻接矩阵做存储结构时,广度优先搜索的代码如下。
对于邻接表的广度优先遍历,代码与邻接矩阵差异不大, 代码如下。
对比图的深度优先遍历与广度优先遍历算法,会发现,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的,只是不同的情况选择不同的算法。
——推荐阅读——
——推荐阅读——
招考公告——新疆社会招聘考试公告
试题资料——2022新疆社会工作相关考题
考试技巧——新疆社会工作笔试备考技巧
社会工作备考——新疆社区招聘考试《公基+社区知识+综合写作》乐享班
社会工作报考——新疆社会工作者报考条件
以上为本文的全部内容,由新疆公务员考试网提供,希望对考生有所帮助!更多新疆公务员招考信息,请加新疆公务员考试交流群,及关注新疆公务员考试招考资讯/新疆人事考试网。
(编辑:Carry)贴心微信客服
新疆华图公众号
10万+
阅读量150w+
粉丝1000+
点赞数