[理学]数据结构第7章.pptVIP

第7章 图;图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。;图是由非空的顶点集合和一个描述顶点之间关系—边的有限集合组成的一种数据结构。可以用二元组定义为： G＝（V，E） 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。;V1;V1;假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶点到自身的边或者弧，即如果vi,vj,则vi≠vj 。对于无向图，边数e的取值范围为0~n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图或无向完全图。对于有向图，弧度e的取值范围是0~n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。具有enlogn条弧或者边的图称为稀疏图。具有enlogn条弧或者边的图称为稠密图。 ;7.1.2 图的基本术语;7.1.2 图的基本术语;在图7-1的G1中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在图7-2的G2中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2;7.1.2 图的基本术语;7.1.2 图的基本术语;7.1.2 图的基本术语;4．子图 对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集 ，E’是E的子集 ，则称图G’是G的一个子图。;7.1.2 图的基本术语;5．连通图和强连通图 在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图。否则，将其中的极大连通子图称为强连通分量。 ;6．生成树 在含有n个顶点的图G中，如果G是包含n个顶点的极小连通子图，该子图只有n-1条边，这样的图称为连通图的生成树。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵包含n个顶点的生成树仅有n-1条边，如果少于n-1条边，则改图是非连通的。;6．生成树 图7-6为图7-4中无向图G3的生成树。;7．网 如果在图的边或者弧上增加具有一定意义的数，这些数称为权，权通常表示一个顶点到另一个顶点的距离或者花费，带有权的图称为网。一个网如图所示。;7.2 图的存储结构;7.2.1 邻接矩阵;7.2.1 邻接矩阵;7.2.1 邻接矩阵;; 图的邻接矩阵具有以下性质： （1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。 （2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。 （3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。 （4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。;7.2.2 邻接链表;在邻接表表示中有两种结点结构，如图7-10所示。 顶点域 边表头指针 邻接点域 指针域;7.2.2 邻接链表;7.2.2 邻接链表;7.2.2 邻接链表;7.3 图 的 遍 历;7.3.1 深度优先有哪些信誉好的足球投注网站;7.3.1 深度优先有哪些信誉好的足球投注网站;7.3.1 深度优先有哪些信誉好的足球投注网站;7.3.2 广度优先有哪些信誉好的足球投注网站;7.3.2 广度优先有哪些信誉好的足球投注网站;7.3.2 广度优先有哪些信誉好的足球投注网站;;7.4 最小生成树;7.4 最小生成树;7.4.1 普里姆(Prim)算法;图7-16 Prim 算法构造最小生成树的过程示意图 ;7.4.2 克鲁斯卡尔(Kruskal)算法;图7-17 Kruskal 算法构造最小生成树的过程示意图 ;7.5 最 短 路 径;表7-1 ;7.5.2 每一对顶点之间的最短路径;7.5.2 每一对顶点之间的最短路径; 7.6 AOV网拓扑排序;7.6.1 AOV网;7.6.2 AOV网拓扑排序;7.6.2 AOV网拓扑排序;7.6.2 AOV网拓扑排序;7.6.2 AOV网拓扑排序;7.6.2 AOV网拓扑排序