扫码获取更多资源

●图的类型定义

图是一种较线性结构和树结构更为复杂的数据结构。在线性结构中，数据元素之间仅 有线性关系；在树结构中，数据元素之间有着明显的层次关系，虽然每一层上的数据元素可 能和下一层中的多个元素(孩子)相关，但只能和上一层中的一个元素(双亲)相关；而在图 结构中，结点之间的关系可以是任意的，任意两个数据元素之间都可能相关。

2、数据元素：数据元素是数据的基本单位，但不是最小单位。在程序中通常作为一个整体来进行考虑和处理，又称为记录。

在图中，如果不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单 图 (Simple Graph) o在数据结构中讨论的图均为简单图。图7-1给出了非简单图的示例。

图的定义

图(Graph)由两个集合V和VR组成，记为G=(V, VR),其中：V是顶点(Vertex)的 有穷非空集合，VR是V中顶点偶对的有穷集，顶点偶对称为边或弧。通常，也将图G的顶 点集和边集分别记为V(G)和VR(G)O如果VR(G)为空，则图G只有顶点而没有边。

图的相关概念

如果顶点V.和Vj之间的边没有方向，则称该边为无向边，用无序偶对(Vj, Vj)表示，该 图称为无向图(Undirected Graph) 9如图7-2(a)所示

生成树和生成森林

具有n个顶点的连通图G的生成树(Spanning Tree)是包含G中全部顶点的一个极小 连通子图。它含有图中全部顶点，但只有足以构成一棵树的n—1条边。如果在生成树中添 加任意一条属于原图中的边，则必定会产生回路，其原因是新添加的边使其所依附的两个顶 点之间有了第二条路径；如果在生成树中减少任意一条边，则必然成为非连通图。图7-8(a) 所示连通图G5的一棵生成树如图7-8(b)所示，而图7-8(c)给岀了两棵非生成树。

图中顶点位置

在线性表中，元素在表中的编号就是其在序列中的位置，因而其编号是唯一的；在树 中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；在图中，任何两个 顶点之间都可能存在关系，顶点没有确定的先后次序，所以顶点编号是不唯一的。为了定义 操作的方便，将图中顶点按任意顺序排列起来(这个排列和关系无关)，例如存储结构中顶点 的存储顺序构成了顶点之间的相对次序，也就是用顶点的存储顺序表示该顶点在图中的 位置。

联系我们：