数据结构与算法6讲解.ppt

;6.1 图的基本概念及特性;;1.有向图和无向图 若E(G)中的顶点偶对是有序的，则这些有序偶对就形成了有向边，此时图G称为有向图。其中，有向边也简称为弧。在有向图G中，对于一条从顶点vi到顶点vj的弧，记作vi, vj并有vi, vj∈E(G)，称vi为弧尾，vj为弧头。例如，图6-1（a）中所示的G1是一个有向图，其顶点集合V(G1)={v0, v1, v2, v3, v4}，边集合E(G1)={v0,v1, v0,v2, v1,v4, v2,v0, v3,v0, v3,v2}。 ;2.顶点的度、入度和出度 在无向图G中，若存在(vi, vj)∈E(G)，则称顶点vi和顶点vj互为邻接点，即顶点vi和顶点vj相邻接，或者说顶点vi、vj与边(vi, vj)相关联。与顶点vi相关联的边的数目称为顶点vi的度，记作D(vi)。例如，图6-1（b）所示的无向图G2中，各顶点的度分别为：D(v0)=3，D(v1)=D(v2)=D(v3)=2，D(v4)=1。 在有向图G中，若存在vi, vj∈E(G)，则称顶点vi邻接到顶点vj，或顶点vj邻接自顶点vi。以顶点vi为弧头的弧的数目称为顶点vi的入度，记作ID(vi)；以顶点vi为弧尾的弧的数目称为vi的出度，记作OD(vi)；顶点vi的入度和出度之和称为vi的度，记作D(vi)。 ;3.路径、路径长度和回路 在图G中，若存在一个顶点序列(,, …, )，使得对于任意0≤jn-1有（若G为有向图）或（若G为无向图），则该序列是从顶点到顶点的一条路径。显然，从一个顶点到另一个顶点的路径不一定唯一。 一条路径中边的数目称为路径长度。 在一条路径中，若一个顶点至多只经过一次，则该路径称为简单路径；若组成路径的顶点序列中第一个顶点与最后一个顶点相同，则该路径称为回路（或环）；在一个回路中，若除第一个顶点与最后一个顶点外，其他顶点只出现一次，则该回路称为简单回路（或简单环）。 ;4.连通图 对无向图，若至少存在一条从顶点vi到顶点vj的路径，则称顶点vi和顶点vj是连通的。若无向图G中任意两个顶点都是连通的，则称G为连通图。 对有向图，若存在从顶点vi到顶点vj的路径或存在从顶点vj到顶点vi的路径，则称顶点vi和顶点vj是单向连通的；若两条路径同时存在则称顶点vi和顶点vj是强连通的。有向图G中，若任意两个顶点都是单向连通的，则称G是单向连通图；若任意两个顶点都是强连通的，则称G为强连通图。 ;5.子图、连通分量和强连通分量 对于图G、G，若满足且，则G是G的子图。也就是说，从图G的顶点集合中选出一个子集并从边集合中选出与该顶点子集相关的一些边所构成的图，就是图G的子图。 一个无向图的极大连通子图称为该无向图的连通分量；一个有向图的极大强连通子图称为该有向图的强连通分量。这里的“极大”是指向连通子图或强连通子图中再添加一个顶点，该子图就不再连通或强连通。显然，若一个图本身就是连通图或强连通图，那么它的连通分量或强连通分量就是图本身，具有唯一性。若一个图本身是非连通图或非强连通图，那么它的连通分量可能有多种形式。 ; 例如，图6-2（a）和图6-2（c）分别是非连通图和非强连通图，对应的两种形式的连通分量和强连通分量分别如图6-2（b）和图6-2（d）所示。 ;6.权和带权图 与前一章学习的树中结点的权相似，可以为一个图中的每条边标上一个具有某种意义的实数，该实数就称为是边的权。通常用边的权表示从一个顶点到另一个顶点的代价。边上带权的图就称为带权图。 ;7.生成树和最小生成树 若无向图G的一个子图G是一棵包含图G所有顶点的树，则G称为图G的生成树。生成树本身是一棵树，具备树的所有性质。对于树中的任一结点，根结点都是其祖先，因此树中的任意两个结点都是连通的，即子图G是连通图。另一方面，子图G与图G具有相同的顶点集合，而子图G的边集合是图G边集合的子集，因此图G必然也是连通图。也就是说，只有连通图才有生成树。 连通图的生成树不具有唯一性，从不同的顶点出发或采用不同的遍历算法，可以得到不同的生成树。 ; 例如，图6-3（b）所示的就是根据图6-3（a）得到的两种不同形式的生成树。在所有形式的生成树中，边上的权之和最小的生成树，称为最小生成树。 ;;;;6.2 图的抽象数据类型和表示方式 ;6.2 图的抽象数据类型和表示方式 ;6.2 图的抽象数据类型和表示方式 ;6.2 图的抽象数据类型和表示方式 ;6.2 图的抽象数据类型和表示方式 ;6.2 图的抽象数据类型和表示方式 ;;;邻接链表可以看作是图的一种链式存储结构。