lecture 6 graph algorithms

《lecture 6 graph algorithms》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六部分图算法（Graphalgorithms）6．1图图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.6.1.1图的基本概念图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={v

2、vÎ某个数据对象}是顶点的有穷非空集合；E={(v,w)

3、v,wÎV}是顶点之间关系的有穷集合，也叫做边(edge)集合。l有向图与无向图若图中的每条边都是有方向的，则称为有向图。有向边也称为弧。若图中的每条边都是没有方向的，则称为无向图。例6.1G1=(V1E1)其中:V1={v1

4、,v2,v3,v4}E1={,,,}G2=(V2E2)其中:V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}有向图G1无向图G219l完全图对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1)，则称其为有向完全图。l邻接顶点若（v,v’）是一条无向边，则称顶点v和v’互为邻接点，或称v和v’相邻接，并称边（v,v’）关联于顶点v和v’，或称（v,v’）与顶点v和v’相关联。l顶点的度

5、一个顶点v的度是与它相关联的边的条数。记作Deg(v)。l顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。TD(v)=ID(v)+OD(v)有n个顶点，e条边或弧的图，有e=l子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’ÍV且E‘ÍE,则称图G’是图G的子图。l路径在图G＝(V,{E})中,若存在一个顶点序列vp1,vp2,…,vpm，使得(v,vp1)、(vp1,vp2)、...、(vpm,v’)均属于E，则称顶点v到v’存在一条路径。若一条路径上除了v和v’j可以相同外，其余顶点均不相同，则称此路径为

6、一条简单路径。起点和终点相同的路径称为简单回路或简单环。l图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。19l强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。v5v1v2v3v4v5v1v2v4v5v1v2v3v3v4v1v2G1的两个强连通分量G2的子图v1§权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。12356874ABDCE10

7、796671231516603045358040756.1.2图的存储结构图的数据表示方式有多种，以下介绍较为常用的四种：一、邻接矩阵（AdjacencyMatrix）邻接矩阵是将图中的n个顶点（Vertices），以一个n×n的二维矩阵来表示，其中若A(i,j)=1，则表示图中有一条边（Vi,Vj）存在。反之，A(i,j)=1则没有（见图6.1～图6.4）。例6．219图6.1图的邻接矩阵表示法无向图的邻接矩阵具有对称性，且对角线上元素都为0，所以在图中只需存储上三角或下三角即可，所需要存储空间为n(n-1)/2。读者要注意的是：（1）若要求无向图中某一顶点相邻边的数目（即度），

8、则要算邻接矩阵中某一列所有1的和或某一行所有1的和。例如要求例（1）中顶点2的相邻边数，可从第2列或第2行，知其顶点2的相邻边数（度）是3。（2）若要求有向图的入度或出度。邻接矩阵中列中1的和便是出度，而行中1的和，便是入度。二、邻接表（AdjacencyList）邻接表是将图中的每个顶点都形成单链表的表头，而在每个链表表头后的结点表示它们之间有边相连。例6.3图6.2每个结点数据结构如图6.1.2.6所示。图6.319在无向图中，若有n个顶点，m个边，则形成n个链表表头，2m个结点（对称）。在有向图中，则有n个链表表头，及m个顶点。图6.4例6.4图6.5图的邻接表表示法三、邻接

9、多重表（AdjacencyMultilist）每个边均以一个结点表示，但这个结点可同时存在于两个链表中，结点的结构如下：19LINK1LINK2MV1V2forV1forV2M为一个位的标记字段，用以表示该边是否已被搜索过。V1及V2表示该边的两个顶点。LINK1字段是一个指针，若尚有其他顶点与顶点V1相连，则LINK1指向“该顶点与顶点V1所形成的边结点”，否则指向0（null）。LINK2字段也是一个指针，若尚有其他顶点与顶点V2相连，则LINK2指向“该顶点与顶