【数据结构】图1——图的基本概念和术语、类型定义

大家好，欢迎来到IT知识分享网。

图的定义

图的术语

1、有向图：每条线都是有方向的。

2、无向图：每条线都是无方向的。

3、完全图：任意两个点都有一条边相连。

3、稀疏图：有很少边或弧的图(e<nlogn) 。

4、稠密图：有较多边或弧的图。

5、网：边/弧带权的图。

9、有向树：有向图中仅1个顶点的入度为0，其余顶点的入度均为1。

10、路径：接续的边构成的顶点序列。

11、路径长度：路径上边或弧的数目/权值之和。

12、回路(环)：第一个顶点和最后一个顶点相同的路径。

13、简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

14、简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。

15、连通图(强连通图)：在无(有)向图G=(V, {E} )中，若对任何两个顶点v、u 都存在从v到u的路径，则称G是连通图(强连通图)。

16、权：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。

17、图：带权的图称为网。

18、子图：设有两个图G= (V, {E}) 、G1= (V1, {E1})，若V1⊆V，E1⊆E，则称G1是G的子图。

21、极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

22、生成树：包含无向图G所有顶点的极小连通子图。

23、生成森林：对非连通图，由各个连通分量的生成树的集合。

图的抽象数据类型定义

ADT Graph{ 
     数据对象V：具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={ 
    VR} VR={ 
    <v,w>|<v,w>|v,w∈V∧p(v,w), <v,w>表示从v到w的弧， P(v,w)定义了弧<v,w>的信息 } 基本操作P：Create_Graph():图的创建操作。 初始操作：无。 操作结果：生成一个没有顶点的空图G。 GetVex(G,v):求图中的顶点v的值。 初始条件：图G存在，v是图中的一个顶点。 操作结果：生成一个没有顶点的空图G。 ...... CreateGraph(&G,V,VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DFSTraverse(G) 初始条件：图G存在 操作结果：对图进行深度优先遍历 BFSTraverse(G) 初始条件：图G存在 操作结果：对图进行广度优先遍历 }ADT Graph