十二、图的遍历--(1)图的遍历和生成树

时间:2021-04-11 11:37:47

摘自计蒜客:http://www.jisuanke.com/course/35/7315

什么是图的遍历呢?从图的某个顶点出发,沿图中的路径依次访问图中的所有顶点,并且使得图中所有顶点都恰好被访问一次,

这个过程即为图的遍历。需要注意的是,接下来讨论图的遍历时,都是特指在一个连通图上进行遍历。

图的两种最常见的遍历算法:广度优先搜索(BFS)和深度优先搜索(DFS)。

从思路上讲,图的遍历和树或森林的遍历的核心思路很像:都是化繁为简。此前通过对二叉树进行遍历,可以将二叉树转换为

一个线性序列。这就是化繁为简的思路:把树这种非线性结构转化为线性序列。把二叉树的很多问题都转化到线性序列上进行求解。

线性序列是树或森林的一个特例,而树或森林则是图结构的一个特例。防照树的遍历,在对图进行便利的过程中,首先将图这

种复杂的非线性结构,转化为图的一种特例,就是一棵树----生成树(也叫支撑树)。

这样的一棵生成树,具有两个重要的性质:其一,它的根节点便是我们对图进行遍历时的起始顶点;其二,它包含图中的所有

顶点。对于一个图,可能会有很多种合法的生成树。

十二、图的遍历--(1)图的遍历和生成树  十二、图的遍历--(1)图的遍历和生成树

图1                                                                           生成树1

十二、图的遍历--(1)图的遍历和生成树  十二、图的遍历--(1)图的遍历和生成树

图2                                                                            生成树2

十二、图的遍历--(1)图的遍历和生成树  十二、图的遍历--(1)图的遍历和生成树

图3                                                                            生成树3