数据结构（Java语言描述）（第2版）课件 5.1 图的概述

数据结构主讲人：杨丹常州信息职业技术学院5.1图的概述图是一种复杂的非线性结构。在图结构中，对结点的前驱和后继的个数没有任何限制，结点之间的关系是任意的，图中任意两个结点之间都可能有关系，也就是说图结点的关系是多对多的。引言IntroductionPart01图的基本概念图是由结点集合和结点间的关系集合组成的一种数据结构。记作：G=(V，E)其中，V={x│x∈某个数据元素集合}，E={(x,y)|x,y∈V}。V是有限的非空集合，V中的元素称为顶点（Vertex）或结点，E是V中顶点偶对(x,y)的集合，E中的元素称为边（Edge）。图说明图的基本概念图的基本概念5示例左图中，顶点集合V＝{v1,v2,v3,v4,v5}；边的集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}。无向图与有向图6无向图

若图G中的每条边都是没有方向的，则称G为无向图。无向图中边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对(x,y)和(y,x)表示图中的同一条边。无向图若图G中的每条边都是有方向的，则称G为有向图。有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对<x,y>和<y,x>表示的是图中不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。有向图有向图有向图7示例左图中，顶点集合V＝{v1,v2,v3,v4}；边的集合E＝{<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。①若(x，y)或<y，x>是E(G)中的一条边，则要求x≠y；②不允许一条边在图中重复出现；③不允许在同一个图中既有有向边又有无向边。注意完全图8无向图

若G是具有n个顶点e条边的无向图，则顶点数与边数的关系为0≤e≤n(n-1)/2。把恰有n(n-1)/2条边的无向图称为无向完全图。也就是说，在无向完全图中，任意两个顶点之间都有一条边。无向完全图有向图完全图9无向图若G是具有n个顶点e条边的有向图，则顶点数与边数的关系为0≤e≤n(n-1)。把恰有n(n-1)条边的有向图称为有向完全图。也就是说，在有向完全图中，任意两个顶点之间有方向相反的两条边。有向完全图有向图01无向边和顶点若(x,y)是一条无向边，则称顶点x和y互为邻接顶点，或称x和y相邻接；并称(x,y)依附或关联于顶点x和y，或称(x,y)与顶点x和y相关联。02有向边和顶点若<x,y>是一条有向边，则称顶点x邻接到y，顶点x邻接于顶点y；并称边<x，y>关联于x和y或称<x,y>与顶点x和y相关联。边与顶点的关系度无向图中顶点v的度无向图中顶点v的度是关联于该顶点的边的数目，记为D(v)。有向图顶点v的入度有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。有向图顶点v的出度有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)。有向图顶点v的度有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。顶点的度无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系：顶点的度12无向图有向图D(v1)=2，D(v2)=3，D(v3)=3，D(v4)=2，D(v5)=2。ID(v1)=1，OD(v1)=2，D(v1)=3；ID(v2)=1，OD(v2)=0，D(v2)=1；ID(v3)=1，OD(v3)=1，D(v3)=2；ID(v4)=1，OD(v4)=1，D(v4)=2。路径13无向图在无向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均属于E(G)，则称该序列为顶点vp到vq的一条路径。无向图的路径有向图V3V1V2V4V5路径14无向图在有向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得有向边<vp,vi1>，<vi1,vi2>，…，<vim,vq>均属于E(G)，则称该序列为顶点vp到vq的一条路径。有向图的路径有向图V1V2V4V3路径15路径长度定义为该路径上边的数目。起点和终点相同的路径称为回路。起点和终点相同的简单路径称为简单回路或简单环。在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。若一条路径除两端顶点可以相同外，其余顶点均不相同，则称此路径为一条简单路径。02030104子图

无向图和它的子图有向图和它的子图连通图和连通分量(a)无向图(b)无向图的两个连通分量①任何连通图的连通分量只有一个，即是其自身；②非连通的无向图有多个连通分量。注意在无向图G中，若从顶点x到顶点y有路径，则称x和y是连通的。若在无向图G中，任意两个不同的顶点x和y都连通(即有路径)，则称G为连通图。无向图G的极大连通子图称为G的连通分量。强连通图和强连通分量有向图G中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图。有向图的极大强连通子图称为G的强连通分量。(a)有向图(b)有向图的两个连通分量①强连通图只有一个强连通分量，即是其自身；②非强连通的有向图有多个强连分量。注意网络有些图的边附带有数据信息，这些附带的数据信息称为权。第i条边的权用符号wi表示。权可以表示两个顶点之间的距离、花费的代价、所需的时间等具有某种意义的数。若将图的每条边都赋上一个权，则称这种图为带权图，也称为网络。Part02图的抽象数据类型描述及定义图的抽象数据类型主要包括两个方面：顶点集合和边集合上的操作。图上常见的操作有：插入顶点、插入边、删除边、查找、获取下一个邻接点、深度遍历、广度遍历等。图的抽象数据类型描述及定义图的抽象数据类型描述及定义T为泛型，表示图中数据元素的数据类型。Java语言约定，T的实际参数必须是类，不能是int、double、char等基本