《第7章图part1》由会员分享，可在线阅读，更多相关《第7章图part1（48页珍藏版）》请在金锄头文库上搜索。
1、第七章第七章 图图 主讲：戚玉涛主讲：戚玉涛第七章 图v7.1 图的定义与基本术语图的定义与基本术语 v7.2 图的存储结构图的存储结构 v7.3 图的遍历图的遍历 v7.4 图的连通性问题图的连通性问题 v7.5 有向无环图的应用有向无环图的应用 v7.6 最短路径最短路径 图的定义和术语 v图（Graph）是一种比线性表和树更为复杂的数据结构结点之间的关系可以是任意的，不受限制，图中结点之间的关系可以是任意的，不受限制，图中任意两个元素之间都可能相关。任意两个元素之间都可能相关。图有着更为广泛的应用，已经渗透到计算机、逻图有着更为广泛的应用，已经渗透到计算机、逻辑学、物理、化学、通信、甚至
2、日常生活中，图辑学、物理、化学、通信、甚至日常生活中，图论是计算机的重要理论分支。论是计算机的重要理论分支。图的定义和术语v图(Graph)：G由两个集合 V 和 E 组成，记为G(V, E)。 v其中： V：是顶点的非空有限集 E：是边的非空有限集合，即两个顶点之间关系的有限集合，边是顶点的无序偶或有序偶 弧：有向边也称为弧，弧是顶点的有序偶无向图v无向图：所有顶点偶对是无向图：所有顶点偶对是无序的无序的ViVj边边(Vi,Vj)或或(Vj,Vi)顶点顶点Vi与与Vj互为邻接点互为邻接点 G= (V，E)V= V1,V2, V3, V4 E= (V1, V2), (V1, V3), (V1,
3、 V4), (V2, V3), (V2, V4)V1V3V4V2无向图中代表边的无序顶点对通常用圆括号括无向图中代表边的无序顶点对通常用圆括号括起来起来,用以表示一条无向边。用以表示一条无向边。 有向图v有向图：所有顶点偶对是有向图：所有顶点偶对是有序的有序的ViVj弧弧 Vi, 弧尾弧尾( (起始点起始点) )ViVi邻接到邻接到VjVjVjVj邻接自邻接自ViVi弧头弧头( (终端点终端点) )G=(V，E)V= V1,V2, V3, V4 E= , , , , V1V3V4V2有向图中代表弧的有序顶点对通常用尖括号括有向图中代表弧的有序顶点对通常用尖括号括起来。起来。子图v子图：设有两个
4、图G=(V,E)，G=(V,E)，若VV 且 EE，则称G为G的子图。V1V3V4V2G V1G V1V4V2G V1V2G图的边数v设图中顶点数为设图中顶点数为n n，边数为，边数为e e，则：，则：有向图：有向图：0en(n-1)无向图：无向图：0en(n-1)/2V1V3V4V2注意：注意：本章不讨论下面两种图本章不讨论下面两种图多重图：多重图：包含重复边的图包含重复边的图自身带环的图：自身带环的图：和包含端点是和包含端点是同一个顶点的边的图。同一个顶点的边的图。完全图v有向完全图：有向完全图： e = n(n-1)v无向完全图：无向完全图： e = n(n-1)/2v稀疏图：稀疏图：对
5、于有很少条边的图对于有很少条边的图(enlogn)， 反之称反之称为为稠密图稠密图。 V1V2V3V4V1V2V3V4有向完全图 e12无向完全图 e6顶点的度v顶点顶点V的度的度TD(V)：关联于顶点关联于顶点V的边或弧的数目的边或弧的数目v有向图顶点有向图顶点V的入度的入度ID(V)：以顶点以顶点V为弧头的边数为弧头的边数v有向图顶点有向图顶点V的出度的出度OD(V)：以顶点以顶点V为弧尾的边数为弧尾的边数V1V3V4V2TD(V1)=4ID(V1)=1OD(V1)=3路径与回路v路径：从一个顶点V出发，沿着边/弧到达另一个顶 点V所经历的顶点序列： V，Vi,1，Vi,2，.，Vi,m，
6、V 其中（Vi,j-1, Vi,j）或 E (2jm)v回路(环)：起点和终点是同一个顶点的路径。v简单路径/简单环：除了起点和终点外，路径上其余顶点不重复出现的路径/环。v路径的长度：路径上边/弧的数目。权与网v在实际应用中，有时图的边或弧上往往与具有一定意义的数在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为有关，即每一条边都有与它相关的数，称为权权，这些权可以，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做这种带权的图叫做赋权图赋权图或或网网。 V1V2V4V6V
7、5V33103831415462有向带权图有向带权图V1V3V4V2123875无向带权图无向带权图图的连通性v无向图G的连通性 连通：连通：如果如果G中顶点中顶点Vi与与Vj之间有路径，之间有路径，称称Vi与与Vj是连通的是连通的 连通图：连通图：无向图无向图G中任意两个顶点之间都中任意两个顶点之间都连通连通 连通分量：连通分量：无向图无向图G的的极大连通子图极大连通子图称为称为G的一个连通分量。的一个连通分量。V1V3V4V2AEFDCB连通图G1非连通图G2ADCBEFG2的两个连通分量非连通图连通分量连通分量：连通分量：极大连通子图极大连通子图图的连通性v有向图有向图G的连通性的连通性
8、强连通：强连通：如果如果Vi到到Vj有路径，有路径，Vj到到Vi也有路径，称也有路径，称Vi到到Vj是强连通的是强连通的强连通图：强连通图：有向图有向图G中任意两个顶点之间都强连通中任意两个顶点之间都强连通强连通分量：强连通分量：有向图有向图G的的极大强连通子图极大强连通子图称为称为G的一个强的一个强连通分量连通分量弱连通图：弱连通图：如果有向图如果有向图G去掉每条边的方向后得到的无向去掉每条边的方向后得到的无向图是连通的，称图是连通的，称G是弱连通图是弱连通图单向连通图：单向连通图：如果如果G中任意两个顶点之间至少一个可达另中任意两个顶点之间至少一个可达另一个，则称一个，则称G是单向连通图是
9、单向连通图强连通图一定是单向连通图；强连通图一定是单向连通图；单向连通图一定是弱连通图。单向连通图一定是弱连通图。有向图G的连通性：V1V4V2V3V1V4V2V3V1V4V2V3强连通图单向连通图弱连通图v1、v4无法到达无法到达非强连通图非强连通图G G3 3G3G3的两个强连通分量的两个强连通分量V1V3V4V2V1V3V4V2V3V1V4V2强连通分量：强连通分量：极大强连通子图极大强连通子图图的生成树v图论中对树的定义：图论中对树的定义：无回路的连通图无回路的连通图（n个顶点，n-1条边）无向连通图的生成树：无向连通图的生成树：设设G（V，E）是具有）是具有n个顶点个顶点的无向连通图
10、，的无向连通图，G的生成树是的生成树是G的一个的一个极小连通极小连通子图，子图，它包含了它包含了G的的n个顶点及构成树的个顶点及构成树的n-1条边。条边。V1V7V4V3V5V6V2V1V7V4V3V5V6V2V1V7V4V3V5V6V2对非连通图G而言，其每个连通分量都具有相应的生成树，构成了G的生成森林。例：例：有有n个顶点的有向强连通图最多需要多少条个顶点的有向强连通图最多需要多少条边？最少需要多少条边？边？最少需要多少条边？ 有有n个顶点的有向强连通图最多有个顶点的有向强连通图最多有n(n-1)条边条边( (构成一构成一个有向完全图的情况个有向完全图的情况) )；最少有；最少有n条边条
11、边( (n个顶点依次首个顶点依次首尾相接构成一个环的情况尾相接构成一个环的情况) )。 第七章 图v7.1 图的定义与基本术语图的定义与基本术语 v7.2 图的存储结构图的存储结构 v7.3 图的遍历图的遍历 v7.4 图的连通性问题图的连通性问题 v7.5 有向无环图的应用有向无环图的应用 v7.6 最短路径最短路径 图的存储结构v1、邻接矩阵表示法(数组表示法)v2、邻接表表示法v3、有向图的十字链表存储表示v4、无向图的邻接多重表存储表示邻接矩阵表示法(数组表示法)v用一个一维数组存放图的顶点数据用一个一维数组存放图的顶点数据v用一个矩阵用一个矩阵AnnAnn 来存放图的边的信息来存放图
12、的边的信息有向有向/ /无向图无向图: : A i j A i j 0 0 反反之之1 1 若若V 或或 (V(Vi i, , V Vj j) ) E(G)E(G)有向有向/ /无向网无向网: : A i j A i j 或或 0 0 反之反之w wijij 若若V 或或 (V(Vi i, , V Vj j) ) E(GE(G) )图的邻接矩阵定义：图的邻接矩阵定义：# define max_n 20 /最大顶点数最大顶点数# define INFINITY INT_MAX /表示极大值表示极大值typedef enumDG, DN, AG, AN GraphKind; /图种类标志：图种类标
13、志：/DG-有向图有向图/DN-有向网有向网/AG-无向图无向图/AN-无向网无向网图的邻接矩阵定义：图的邻接矩阵定义：typedef struct ArcCell/弧结点与矩阵的类型弧结点与矩阵的类型 VRType adj; /VRTypeVRType为弧的类型。图为弧的类型。图-0,1;-0,1;网网-权值权值 InfoType *Info; /与弧相关的信息的指针与弧相关的信息的指针, ,可省略可省略ArcCell, AdjMatrixmax_nmax_n;typedef struct/图的类型图的类型 VertexType vexsmax_n;/顶点向量顶点向量 AdjMatrix a
14、rcs;/邻接矩阵邻接矩阵 int vexnum, arcnum;/顶点数，边数顶点数，边数 GraphKind kind；/图类型图类型MGraph; 此项可以省略V1V7V4V3V5V6V2V1V2V3V4V5V6V70123456012345600111000110001112100000131000000401000105010010060110000G.arcs=G.vexs=无向图的邻接矩阵无向图的邻接矩阵存放顶点的数组表示边的矩阵V1V2V3V4V5V6V7V8012345670123456700111000010010110020000010030010011040000000
15、1500001010600000001700000000G.arcs=G.vexs=V1V7V4V3V5V6V2V8有向图的邻接矩阵有向图的邻接矩阵存放顶点的数组存放顶点的数组表示弧的矩阵表示弧的矩阵V4的出边邻接点V4的入边邻接点无向图邻接矩阵的特点v对称矩阵：因此，按照压缩存储的思想，在具体存因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上放邻接矩阵时只需存放上(或下或下)三角形阵的元素即三角形阵的元素即可。可。v顶点Vi的度等于第i行非零元个数，或第i列非零元个数：v矩阵非零元总数等于边数的2倍有向图邻接矩阵的特点v是非对称矩阵v不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，因
16、此，不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。v第i行非零元个数等于顶点Vi的出度；第i列非零元个数等于顶点Vi的入度：v矩阵非零元总数等于边数ABCD01230123014192235836G.arcs=G.vexs=有向网的邻接矩阵示例：有向网的邻接矩阵示例：68314592ADCB邻接矩阵表示法的不足v用邻接矩阵方法存储图，很容易确定图中任用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确意两个顶点之间是否有边相连。但是，要确定图中有多少条边定
17、图中有多少条边,则必须按行、按列对每个则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。是用邻接矩阵存储图的局限性。图的存储结构v1、邻接矩阵表示法(数组表示法)v2、邻接表表示法v3、有向图的十字链表存储表示v4、无向图的邻接多重表存储表示邻接表表示法v邻接表表示法邻接表表示法：图的邻接表存储方法是一种顺序分配与链式图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第一个单链表，第i个单链表中的结点表示依附于顶点个
18、单链表中的结点表示依附于顶点vi的边的边(对有向图是以顶点对有向图是以顶点vi为尾的弧为尾的弧)。每个单链表上附设一个表。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：头结点。表结点和表头结点的结构如下：adjvexnextarcinfodatafirstarc表结点表结点表头结点表头结点data存储顶点存储顶点vi的名称或其他信息的名称或其他信息; firstarc指向链表中第一个指向链表中第一个结点。结点。 adjvex指示与顶点指示与顶点vi邻接的点在图中的位置邻接的点在图中的位置;nextarc指示下一指示下一条边或弧的结点条边或弧的结点; info存储与边或弧相关的信息存
19、储与边或弧相关的信息,如权值等。如权值等。#define max_n 20/最大顶点数最大顶点数typedef struct ArcNode/表结点表结点 intadjvex;/邻接点的下标邻接点的下标 struct ArcNode*nextarc; /后继链指后继链指针针ArcNode;typedef struct VNode/表头结点表头结点 VertexType data;/顶点数据顶点数据 ArcNode *firstarc;/边链头指针边链头指针VNode, AdjListmax_n; typedef struct AdjListvertices;/邻接表邻接表 intvexnum,
20、arcnum; /顶点数和边数顶点数和边数 GraphTypekind；/图种类标志图种类标志ALGraph;V1V7V4V3V5V6V2data0V11V22V33V44V55V66V7891321546010firstarc645021G.vertices无向图的邻接表：无向图的邻接表：adjvex nextarc无向图邻接表的特点v顶点顶点ViVi的度等于的度等于ViVi所引导的单链表的长度所引导的单链表的长度v边结点的个数等于边数的边结点的个数等于边数的2 2倍倍有向图的邻接表：有向图的邻接表：V1V7V4V3V5V6V2V8data0V11V22V33V44V55V66V78V891
21、 32 7 6 54firstarcadjvex nextarc54 2 724 5G.vertices有向图邻接表的特点v顶点顶点ViVi引导的单链表是出边链，链表的长度引导的单链表是出边链，链表的长度等于等于ViVi的出度的出度v找一个顶点的出边容易，找入边需要遍历整找一个顶点的出边容易，找入边需要遍历整个邻接表个邻接表v边结点的个数等于边数边结点的个数等于边数有向图的逆邻接表：有向图的逆邻接表：data0V11V22V33V44V55V66V78V891 32 0 5 01firstarcadjlist nextarcG.vertices01 3 53 74V1V7V4V3V5V6V2V
22、8ADCB68314592data0A1B2C3D4firstarcG.vertices11adjvexnextarcweight43922330518362有向网的邻接表：有向网的邻接表：图的存储结构v1、邻接矩阵表示法(数组表示法)v2、邻接表表示法v3、有向图的十字链表存储表示v4、无向图的邻接多重表存储表示有向图的十字链表存储表示v将有向图的邻接表和逆邻接表结合在一起，就得到将有向图的邻接表和逆邻接表结合在一起，就得到了了有向图有向图的另一种链式存储结构的另一种链式存储结构十字链表十字链表。vexinfofirstoutfirstin表结点表结点头结点头结点tailvex : 弧尾顶点
23、位置弧尾顶点位置headvex : 弧头顶点位置弧头顶点位置tnext : 弧尾相同的下一条弧弧尾相同的下一条弧vexinfo : 顶点的信息顶点的信息firstin : 第一条关联第一条关联入弧入弧结点结点firstout : 第一条关联第一条关联出弧出弧结点结点tailvextnextheadvexhnextarcinfohnext : 弧头相同的下一条弧弧头相同的下一条弧arcinfo : 弧弧的信息的信息v1v2v4v3e1e2e4e5e3e6e70123v1v2v3v40 1e10 2e22 0e33 0 e53 1e63 2 e72 3e4图的存储结构v1、邻接矩阵表示法(数组表示
24、法)v2、邻接表表示法v3、有向图的十字链表存储表示v4、无向图的邻接多重表存储表示无向图的邻接多重表存储表示v邻接表是无向图的一种很有效的存储结构，邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息在邻接表中容易求得顶点和边的各种信息v但在邻接表中，每一条边都有两个结点表示，但在邻接表中，每一条边都有两个结点表示，因此在某些对边进行的操作（例如对搜索过因此在某些对边进行的操作（例如对搜索过的边做标记）中就需要对每一条边处理两遍的边做标记）中就需要对每一条边处理两遍v故引入故引入邻接多重表邻接多重表实现实现无向图无向图的存储结构的存储结构无向图的邻接多重表存储表示v邻接
25、多重表的结构与十字链表相似邻接多重表的结构与十字链表相似vexinfo firstedge头结点头结点vexinfo : 顶点的信息顶点的信息firstedge : 第一条关联边结点第一条关联边结点表结点表结点ivex : 边的第一个顶点位置边的第一个顶点位置jvex : 边的另一个顶点位边的另一个顶点位置置inext : 顶点顶点 i 的下一条关联边的下一条关联边jnext : 顶点顶点 j 的下一条关联边的下一条关联边einfo : 边的信息（可省略）边的信息（可省略）ivex inextjvex jnexteinfomarkmark : 标志域，是否遍历过标志域，是否遍历过无向图的邻接多重表存储表示：
