数据结构学习-【图】
在说图的定义之前 先要说明一下:
线性表中我们把数据元素叫做元素,树中数据元素叫做结点,在图中数据元素,我们称之为顶点。
下面说一下图的定义:
图是由顶点的有穷非空集合和顶点之间的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
注意:图中的 顶点集合不允许为空,但是边集合允许为空。
各种图的定义:
1.无向图
两个顶点之前的边没有方向,称为无向边,改图中所有的边都是由无向边组成的图,叫做无向图。
该图的表示法:
G1(V1,{E1})
顶点集合:V1={A,B,C,D}; 边集合:E1{(A,B),(B,C),(C,D),(D,A),(A,C)}
2.有向图
改图所有的边都是由有向边构成
有向边又叫弧,例如下图顶点B到A的边就有方向,则称这条边有方向,也称为弧,B是弧头,A称弧尾,写成<A,B>
改图的表示为:G2=(V2,{E2})
顶点集合:V2={A,B,C,D}
弧集合:E2={<A,D>,<B,A>,<C,A>,<B,C>}
在无向图中,如果任意两个顶点之间的都存在边,则称改图为无向完全图。
共有n(n-1)/2条边
在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称改图为有向完全图。
共有n(n-1)条边
有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。这些带权的图通常叫做网。