图的基本概念

文章目录

一、为什么要引入图

二、图的定义

三、有向图和无向图

四、有向完全图和无向完全图

五、稀疏图、稠密图、图的权、环、网、子图

六、 连通图与连通分量

七、 图的定义与术语的总结：

八、 图的抽象数据类型：

一、为什么要引入图

• 1、线性表中，数据元素是串起来的，前驱后继
• 2、树形结构中，有这明显的层次关系，但只能是和上一层中的元素有关
• 3、可现实中，人与人之间的关系非常复杂，考虑到多对多的关系就引入图（图是一种更加复杂的数据结构）

二、图的定义

• 顶点：在图中的数据元素
• 边：任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示，可以为空
• 图：由顶点和边组成，表示G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

三、有向图和无向图

• 无向边：顶点vi到vj之间的边没有方向
• 无向图：图中任意两个顶点之间的边都是无向边（7-2-2）
• 有向边：顶点vi到vj之间的边有方向，也叫弧
• 其中vj叫弧头，vi叫弧尾
• 有向图：图中任意两个顶点之间的边都是有向边（7-2-3）
  

注意：

四、有向完全图和无向完全图

无向完全图：任意两个顶点之间都存在边

有向完全图：任意两个顶点之间都存在方向互为相反的两条弧

结论：

五、稀疏图、稠密图、图的权、环、网、子图

• 稀疏图：有很少的边或弧的图，反之称为稠密图（比较模糊的概念，都是相对而言）
• 图的权（Weight）：与图的边或弧相关的数
• 网：带权的图
  
• 图与子图：
  
• 环或者回路：第一个结点到最后一个结点相同的路径
• 简单环：其他顶点不重复出现的回路，反之不是
  

六、连通图与连通分量

连通图：

连通分量：无向图中的极大连通子图

• 1、子图
• 2、连通
• 3、连通子图中含有极大顶点数
• 4、具有极大顶点数的连通子图包含依附于这些顶点的所有边
  
• 有向图的强连通分量：有向图中的极大强连通子图
  

一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一个树的n-1条边

七、图的定义与术语的总结：

• 图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
• 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
• 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
• 图上的边或弧上带权则称为网。
• 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
• 无向图中连通且n个顶点n-1条边叫生成树。有向图中-顶点入度为 0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

八、图的抽象数据类型：