树与图的比较.doc

树和图都是非线性的数据结构。图相对于树来说，是更加抽象和复杂的。可以认为树是图的基础，树是一种更简单意义上的图。在树型结构中，每一个数据元素都可能和下一层中多个元素（即孩子结点）相关，但却只能与上一层中的一个元素（即双亲结点）相关。而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据之间都可能相关。先看一个简单的图。（实线部分）图（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） 一个树肯定是一个连通图，