图
图状结构是一种比树形结构更复杂的非线性结构.在树状结构中,结点间具有分支层次关系,每一层上的结点只能和上一层中的至多一个结点相关,但可能和下一层的多个结点相关.而在图状结构中,任意两个结点之间都可能相关,即结点之间的邻接关系可以是任意的.因此,图状结构被用于描述各种复杂的数据对象,在自然科学,社会科学和人文科学等许多领域有着非常广泛的应用.
8.1 图的基本概念
图的定义和术语
1.图的定义
图(Graph)是由非空的顶点集合和一个描述顶点之间关系――边(或者弧)的集合组成,其形式化定义为:
G=(V,E)
V={vi| vi∈dataobject}
E={( vi,vj)| vi, vj ∈V ∧P(vi, vj)}
其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合,集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线,即偶对(vi,vj)表示一条边.图8.1给出了一个图的示例,在该图中:
集合V={v1,v2,v3,v4,v5};
集合E={(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}.
图8.1 无向图G1 图8.2 有向图G2
2.图的相关术语
(1)无向图.在一个图中,如果任意两个顶点构成的偶对(vi, vj)∈E是无序的,即顶点之间的连线是没有方向的,则称该图为无向图.如图8.1所示是一个无向图G1.
(2)有向图.在一个图中,如果任意两个顶点构成的偶对(vi, vj)∈E是有序的,即顶点之间的连线是有方向的,则称该图为有向图.如图8.2所示是一个有向图G2:
G2=(V2,E2)
V2={v1,v2,v3,v4}
E2={,,,}
(3)顶点,边,弧,弧头,弧尾.图中,数据元素vi称为顶点(vertex );P(vi, vj)表示在顶点vi和顶点vj之间有一条直接连线.如果是在无向图中,则称这条连线为边;如果是在有向图中,一般称这条连线为弧.边用顶点的无序偶对(vi, vj)来表示,称顶点vi和顶点vj互为邻接点,边(vi, vj)依附于顶点vi与顶点vj;弧用顶点的有序偶对来表示,有序偶对的第一个结点vi被称为始点(或弧尾),在图中就是不带箭头的一端;有序偶对的第二个结点vj被称为终点(或弧头),在图中就是带箭头的一端.
(4)无向完全图.在一个无向图中,如果任意两顶点都有一条直接边相连接,则称该图为无向完全图.可以证明,在一个含有n个顶点的无向完全图中,有n(n-1)/2条边.
(5)有向完全图.在一个有向图中,如果任意两顶点之间都有方向互为相反的两条弧相连接,则称该图为有向完全图.在一个含有n个顶点的有向完全图中,有n(n-1)条边.
(6)稠密图,稀疏图.若一个图接近完全图,称为稠密图;称边数很少的图为稀疏图.
(7)顶点的度,入度,出度.顶点的度(degree)是指依附于某顶点v的边数,通常记为TD (v).在有向图中,要区别顶点的入度与出度的概念.顶点v的入度是指以顶点 为终点的弧的数目.记为ID (v);顶点v出度是指以顶点v为始点的弧的数目,记为OD (v).有TD (v)=ID (v)+OD (v).
例如,在G1中有:
TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2
在G2中有:
ID(v1)=1 OD(v1)=2 TD(v1)=3
ID(v2)=1 OD(v2)=0 TD(v2)=1
ID(v3)=1 OD(v3)=1 TD(v3)=2
ID(v4)=1 OD(v4)=1 TD(v4)=2
可以证明,对于具有n个顶点,e条边的图,顶点vi的度TD (vi)与顶点的个数以及边的数目满足关系:
2e=(
(8)边的权,网图.与边有关的数据信息称为权(weight).在实际应用中,权值可以有某种含义.比如,在一个反映城市交通线路的图中,边上的权值可以表示该条线路的长度或者等级;对于一个电子线路图,边上的权值可以表示两个端点之间的电阻,电流或电压值;对于反映工程进度的图而言,边上的权值可以表示从前一个工程到后一个工程所需要的时间等等.边上带权的图称为网图或网络(network).如图8.3所示,就是一个无向网图.如果边是有方向的带权图,则就是一个有向网图.

下一页