可是现实生活中,好多关系不再是一对一或一对多,比如人和人之间的关系,会互相认识,就要考虑多对多的情况。这就是今天要介绍的——图。
图是一种较线性表和树更加复杂的数据结构,在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素都可能相关。先看个图:
图是由顶点的有穷非空集合和顶点之间的边的集合组成,通常表示为:G(V,E),其中G表示一个图,V是图G中的顶点的集合,E是G中边的集合。
对于图的定义我们需要注意:
无向边:若顶点vi到vj之间的边没有方向,则称这条边为无向边,用无序偶对(vi,vj)来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图,如图:
有向边:若从顶点vi到vj的边有方向,则称这条边为有向边,也称为弧,用有序偶< vi,vj >来表示,vi称作弧尾,vj称作弧头。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。有向边用“<>”表示,注意它是有顺序的,第一个为弧尾,第二个为弧头,不能颠倒。
在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。我们之后说到的都是简单图。下面两个图就不是简单图:
在无向图中,如果任意的两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。如下图:
在有向图中,如果任意两个顶点之间都存在互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条弧,如下图:
由以上可以得出这样的结论,对于具有n个顶点和e条边数的图,无向图0<=e<=n(n-1)/2,有向图0<=e<=n(n-1) 。
有很少条边或弧的图称为稀松图,反之称为稠密图。
有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。这种带权的图通常称为网。如下图:
图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复的叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称为强连通图。图中有子图,若子图极大连通这就是连通分量,有向的则称为强连通分量。