第七章图 图的定义 图的存储结构 图的遍历 图的连通性问题 有向无环图 最短路径 关键路径 7.1基本概念 图 结 Graph=(V,R) V=xxEdataobject RRJ VR=x, y>P(x, y)AND(,yEV)) V是顶点的有穷非空集合; VR是两个顶点之间的关系的集合。 顶点:图中的数据元素; 弧、弧头、弧尾:(v1,2),v-弧尾v—弧头
1 第七章 图 • 图的定义 • 图的存储结构 • 图的遍历 • 图的连通性问题 • 有向无环图 • 最短路径 • 关键路径 数 据 结 构 之 图 2 7.1 基本概念 ¾ 图 Graph=(V,R) Graph=(V,R) V={x|x∈dataobject dataobject} R={VR} VR={<x,y>|P(x,y) AND (x,y VR={<x,y>|P(x,y) AND (x,y∈V) } V是顶点的有穷非空集合; VR是两个顶点之间的关系的集合。 顶点：图中的数据元素； 弧、弧头、弧尾：(v1,v2) , v1—弧尾 v2—弧头
有向图:在图G中,边是顶点的有序对,每 条边都用箭头指明了方向,若<VV>是有向 数据结构 图中的一条边,则称V是尾或初始顶点;V是 头或终端顶点,且用从尾到头的箭头表示, v,v1>和<V1V>不同。 >无向图:边是顶点的无序对,<Vi,Vj>和 <VV>表示同一条边。 无向图 有向图 >无向完全G图:如果在无向图中,任何两个顶点都有 条边相连接,则称此图为无向完全图。含有n个顶 数据结构 点,每一个顶点都与其它个n1顶点有边,因此,共有 n(n-1)2条边 有向完全图:在有向图G中,任何两个顶点都有方向 相反的两条弧线连接,若图G中含有个m顶点,则共有 n(n-1)条弧。 无向完全图 有向完全图
2 数 据 结 构 之 图 3 ¾ 有向图： 在图G中，边是顶点的有序对，每 条边都用箭头指明了方向，若<Vi ,Vj >是有向 图中的一条边，则称Vi 是尾或初始顶点；Vj 是 头或终端顶点，且用从尾到头的箭头表示， <Vi , Vj > 和<Vj ,Vi >不同。 ¾ 无向图： 边是顶点的无序对， <Vi,Vj>和 <Vj,Vi>表示同一条边。 V1 V2 V3 V4 V5 有向图 V1 V2 V3 V4 V5 无向图 数 据 结 构 之 图 4 ¾ 无向完全G图：如果在无向图中，任何两个顶点都有 一条边相连接，则称此图为无向完全图。含有n个顶 点，每一个顶点都与其它个n-1顶点有边，因此，共有 n*(n-1)/2条边。 ¾ 有向完全图：在有向图G中，任何两个顶点都有方向 相反的两条弧线连接，若图G中含有个n顶点，则共有 n*(n-1)条弧。 V1 V2 V3 V4 V5 无向完全图 V1 V2 V3 V4 V5 有向完全图
网:如果图G(V,{E})中每条边都赋有反映这 据结构 条边的某种特性的数据,则称此图G是一个网, 其中与边相关的数据称为该边的权,权所反 映的特性,由具体问题决定,例于两点之间 的距离,时间,代f 网 子图:假设有两个图G=(V,{E})和图G=(V 数{E}),如果ⅤV,且E'cE,则称G为G的子图。 据 构 无向图 >邻接点:对于无向图G=(V,{E}),如果边<VV>∈E, 则称顶点和V互为邻接点,边(V,V)依附于顶点V和
3 数 据 结 构 之 图 5 ¾ 网： 如果图G(V,{E})中每条边都赋有反映这 条边的某种特性的数据，则称此图G是一个网， 其中与边相关的数据称为该边的权，权所反 映的特性，由具体问题决定，例于两点之间 的距离，时间，代价。 网 V1 V2 V3 V4 V5 5 3 6 4 8 7 1 2 V1 V2 V3 V4 V5 4 5 6 8 3 数 据 结 构 之 图 6 ¾子 图：假设有两个图G=(V，{E})和图G’ =(V’ ， {E’ })，如果V’ ⊆V，且E’ ⊆E , 则称G’ 为G的子图。 V1 V2 V3 V4 V5 无向图 子图 V1 V2 V5 V1 V5 V4 V3 V2 V2 V1 V1 V2 V5 V3 ¾邻接点： 对于无向图G=(V,{E})，如果边<V,V’ >∈E, 则称顶点V和V’ 互为邻接点，边(V,V’ )依附于顶点V和 V’
度:顶点V的度是和V相关联的边的数目,记为 TD(。 据>入度:如果顶点V是有向图的一个顶点,则称以V为 头的弧的数目为V的入度,记为D(。 出度:如果顶点是有向图的一个顶点,则称以为 尾的弧的数目为V的出度,记为ODD >有向图顶点的度:顶点的度TD(V=D(+OD( 推论:如果顶点V的度为TD(V),那么有n个顶点, e条边或弧的图,满足如下关系 ⑦D(v,) 路径:图中从顶点到顶点v的路径是顶点 的序列(V=V,V1,…,Vm=V),其中 构 Vi∈E,15Jm。 路径的长度:路径上所含边的数目。 之>回路:第一个顶点和最后一个顶点相同的路 径称为回路或环 圆>简单路径:序列中顶点不重复出现的路径称 为简单路径。 简单回路:除第一个和最后一个顶点之外, 其它顶点不重复出现的回路称为简单回路或环
4 数 据 结 构 之 图 7 ¾度：顶点V的度是和V相关联的边的数目，记为 TD(V)。 ¾入度：如果顶点V是有向图的一个顶点，则称以V为 头的弧的数目为V的入度，记为ID(V)。 ¾出度：如果顶点V是有向图的一个顶点，则称以V为 尾的弧的数目为V的出度，记为OD(V)。 ¾有向图顶点的度：顶点V的度TD(V)=ID(V)+OD(V)。 推论： 如果顶点Vi 的度为TD（Vi ），那么有n个顶点， e条边或弧的图，满足如下关系 ∑= = n i i e TD v 1 ( ) 2 1 数 据 结 构 之 图 8 ¾路径： 图中从顶点V到顶点V’ 的路径是顶点 的序列（V=Vi,0, Vi,1, …, Vi,m = V’），其中 （Vi,j-1, Vi,j)∈E，1≤ j ≤m。 ¾路径的长度：路径上所含边的数目。 ¾回路： 第一个顶点和最后一个顶点相同的路 径称为回路或环。 ¾简单路径：序列中顶点不重复出现的路径称 为简单路径。 ¾简单回路：除第一个和最后一个顶点之外， 其它顶点不重复出现的回路称为简单回路或环
连通:在无向图G中,若从顶点V到顶点V有路径, 则称V和V是连通的 据>连通图:若对于图中任意两个顶点v,V∈V 结都是连通的,则称是连通图。 连通分量:指无向图中极大连通子图。 强连通图:在有向图中,如果对每一对v;V; ∈V,V;≠V;,从V到V和从V到V都存在路径,则 称G是强连通图。有向图G的极大强连通子图称为 强连通分量。 不是强连通图 两个强连通分量 生成树 据 定义:设无向图G是含有n个顶点的连通图,则图G 构的生成树是含有n个顶点,且只有m1条边的连通子图 小连通子 n个顶点 图,若再加 n-1条边 条边,必 连通 勾成 10 生成树=→m-1条边
5 数 据 结 构 之 图 9 ¾连通： 在无向图G中，若从顶点V到顶点V’ 有路径， 则称V和V’ 是连 通的。 ¾连 通 图： 若对于图中任意两个顶点 Vi ，Vj ∈V 都是连通的，则称是连通图。 ¾连通分量：指无向图中极大连通子图。 ¾强连通图：在有向图中，如果对每一对Vi ，Vj ∈V ， Vi ≠Vj ，从Vi 到Vj 和从Vj 到Vi 都存在路径，则 称G是强连通图。有向图G的极大强连通子图称为 强连通分量。 1 2 3 4 1 2 3 4 不是强连通图 两个强连通分量 数 据 结 构 之 图 10 ¾ 生成树 定义：设无向图G是含有n个顶点的连通图， 则图G 的生成树是含有n个顶点，且只有n-1条边的连通子图 三要素： n个顶点 n-1条边 连通 生成树 n-1条边 极小连通子 图，若再加 一条边，必 构成环