【数据结构】图的定义及其概念(一)

图主要知识

图的一些概念

什么是图

图是由顶点集合V和边集E组成的集合，记作G=（V，E）。
注意: G中的顶点是有限非空集合. 线性表可以为非空表, 树也可以是空树, 但图不可以是空图. 即图中不能一个顶点也没有.

有向图/无向图

组成图G的E为有向边是, 此时图称为有向图.
假如有两个顶点v1,v2, 此时可记作<v1,v2>, v1可以称作边的头, v2可以称作边的尾.

当两个点互相可达, 可以认为这两个点之间有一条无向边. 由无向边E组成的图G称为无向图.
假如有两个顶点v1,v2, 此时可记作(v1,v2).

简单图/多重图

简单图:

• 不存在重复边(两点间只有一条边)
• 不存在自身(顶点V)到自身的边

多重图和简单图是相对的. 即, 有重复边或者存在自身(顶点)到自身的边.平常遇到的几乎都是简单图.

完全图

对于任意一个无向图边的数量范围(|E|)是0~n(n-1)/2, 当无向图有n(n-1)/2条边是乘务完全图.
简单来说就是任意两个点之间均有边.

子图

若 $V' \subseteq V$V′⊆V且 $E' \subseteq E$E′⊆E, 此时$G' \subseteq G$G′⊆G, 称$G'$G′是G的子图. 即当顶点和边都是另一个图的子集时, 这个图可以称为另一个图的子集.

连通/连通图

在图像图中, 如果两个点之间存在路径, 就称这两个点是连通的;
若图中任意两个点之间都存在路径, 那么可以将这个图称之为连通图, 否则称为非连通图

常见的连通图:

• 环
• 链
  

强连通图/强连通分分量

在有向图中, 若从一个顶点到另一个顶点相互都有路径, 就称这两个点是连通的, 若图中任意两点都是连通的, 就称图是连通图.
在有向图中的连通子图称之为连通分量, 而有向图中的连通子图称之为强连通分量.