LectureGraphalgorithms.docVIP

第六部分 图算法 （Graph algorithms） 6．1 图 图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统. 6.1.1图的基本概念 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中 V = { v | v ( 某个数据对象} 是顶点的有穷非空集合； E = {(v, w) | v, w( V } 是顶点之间关系的有穷集合，也叫做边(edge)集合。 有向图与无向图 若图中的每条边都是有方向的，则称为有向图。有向边也称为弧。若图中的每条边都是没有方向的，则称为无向图。 例6.1 G1 =(V1 E1) 其中: V1 ={v1, v2, v3, v4} E1={v1,v2,v1,v3,v3,v4,v4,v1} G2 =(V2 E2) 其中: V1 ={v1, v2, v3, v4 , v5} E1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)} 有向图G1 无向图G2 完全图 对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1) ，则称其为有向完全图。 邻接顶点 若（v, v’）是一条无向边，则称顶点v和v’互为邻接点，或称v和v’相邻接，并称边（v, v’）关联于顶点v和v’，或称（v, v’）与顶点v和v’相关联。 顶点的度 一个顶点v的度是与它相关联的边的条数。 记作Deg(v)。 顶点 v 的入度 是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。 TD(v)= ID(v)+ OD(v) 有n个顶点，e条边或弧的图，有 e= 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’( V 且 E‘(E, 则称 图G’ 是 图G 的子图。 路径 在图 G＝(V, {E })中, 若存在一个顶点序列vp1, vp2, …, vpm，使得(v, vp1)、(vp1, vp2)、...、(vpm,v’) 均属于E，则称顶点v到v’存在一条路径。若一条路径上除了v 和v’j 可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。 图的连通 在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi 和vj 是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 权 某些图的边具有与它相关的数, 称之为权。这种 带权图叫做网络。 6.1.2 图的存储结构 图的数据表示方式有多种，以下介绍较为常用的四种： 一、邻接矩阵（Adjacency Matrix） 邻接矩阵是将图中的n个顶点（Vertices），以一个n×n的二维矩阵来表示， 其中若A (i,j) =1，则表示图中有一条边（Vi,Vj）存在。反之，A (i,j) =1则没有（见图6.1～图6.4）。 例6．2 图 6. 1 图的邻接矩阵表示法 无向图的邻接矩阵具有对称性，且对角线上元素都为0，所以在图中只需存储上三角或下三角即可，所需要存储空间为n(n-1)/2。读者要注意的是： （1）若要求无向图中某一顶点相邻边的数目（即度），则要算邻接矩阵中某一列所有1的和或某一行所有1的和。例如要求例（1）中顶点2的相邻边数，可从第2列或第2行，知其顶点2的相邻边数（度）是3。 （2）若要求有向图的入度或出度。邻接矩阵中列中1的和便是出度，而行中1的和，便是入度。 二、邻接表（Adjacency List） 邻接表是将图中的每个顶点都形成单链表的表头，而在每个链表表头后的结点表示它们之间有边相连。 例6.3 图 6. 2 每个结点数据结构如图6.1.2.6所示。 图 6.3 在无向图中，若有n个顶点，m个边，则形成n个链表表头，2m个结点（对称）。在有向图中，则有n个链表表头，及m个顶点。 图 6.