树与图的比较
树和图都是非线性的数据结构。图相对于树来说,是更加抽象和复杂的。可以认为树是图的基础,树是一种更简单意义上的图。
在树型结构中,每一个数据元素都可能和下一层中多个元素(即孩子结点)相关,但却只能与上一层中的一个元素(即双亲结点)相关。而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据之间都可能相关。
先看一个简单的图。(实线部分)
图(1)
这个简单的图同时是一棵简单的树。我们首先根据树的结构给出相关概念。 AB ……称之为树的结点。在这里我们把D 结点看做树的根结点,那么这个树就是一个简单的二叉树。则,A 结点和C 结点就可以称为D 结点的子树或孩子,D 结点是A 结点和C 结点的双亲。在这里,结点拥有的子树个数称为结点的度。因为我们把D 结点看做根结点,也就是说除去叶子节点,每个结点的度都是2. 。在树中,无论从哪一个结点出发,按着一定得路径总能遍历完所有的结点。对于一个拥有n 个结点的树来说,它就拥有n-1条边,这样才能保证形成一个树,才能保证可以从任意结点遍历所有结点。
我们在根据图型结构给出相关概念。图中的概念比树中较多,但本质上是相通的。 AB ……称为图的顶点。在图中没有所谓的根结点问题。每个顶点都是独立的,并不附属于其他任何顶点。这就与树中的双亲和孩子结点有一定区别。在这样一个图中,顶点之间的连线时无向的,此时的图称为无向图,顶点之间的连线称为边。上文提到树中,结点拥有的子树个数称为结点的度。在图中,每个顶点射出(射入)的边都称为顶点的度。(在有向图中有入度和出度之分)
如果我们把上图中的AB ,DG 之间做两条连线的话,如上图虚线所示。这样一连接,图(1)
就不再是一个树了,而变身为一个比较复杂的图。至此我们发现,图中的边更加复杂,这也就使得顶点之间的连接更加简单方便。但这样会给遍历所有顶点带来麻烦,在此不再叙述。
图(1)是比较简单的图,图中任意两个顶点之间都是连通的。所谓连通,就是指两个顶点之间有路径。这个路径可以是直接(AB )的,也可以是间接(AC )的。显然,在未加虚线时,每个顶点之间也是连通的,不过就是少了两条直接的路径而已。加上虚线所示的两条直接路径,使得寻找顶点之间的连通路径更加方便快捷。
现在我们把上图改作图(2)所示,再看一下它的特征。
对于这样一个连通图,它有7个顶点,共9条边。其中在AB 之间出现了不唯一的路径,我们可以从A 顶点直接到B 顶点,也可以从A 经D 、C 再到B 顶点。而且在所有组成环的顶点,都有不同路径出现。这就意味着要从一个顶点通向另一个顶点,可能会有不同的路径可循。如果我们把所有双向的路径都化简,使任意两个顶点之间都存在且只存在唯一的路径。就会得到图(3)所示
在图(3)中,还是7个顶点,但只有6条边,但任意两个顶点之间依然是连通的。这就是图(2)连通图的极小连通子图。我们看到这个极小连通子图中包含所有的顶点,但只有足以构成一棵树的边(可参照上文树的介绍),这样的连通子图称作连通图的生成树。对于一个拥有n 个顶点的连通图,它的生成树包含n 个顶点,n-1条边。
综上,可以得出以下结论:
(1) 一个树肯定是一个连通图,但并不是所有的连通图都是树。
(2) 对于n 个顶点的图,要想构成连通图,它必须首先成为一棵树,即,n 个顶点的连通图至少要拥有n-1条边。