数据结构-图剖析.ppt

第七章 图 7.1 图的基本概念 7.1.1图的定义 图中的数据元素称为顶点。在顶点集合V中，第i个顶点记作vi 图中两个顶点vi和vj之间有关联关系，称作顶点vi和vj之间有一条边。在边集合E中，第k条边记作ek=vi,vj。 图是由顶点的非空有限集合与顶点间关系集合构成的数据结构。记作G=(V,E)。其中，V为顶点集合，E为顶点间关系——边的集合。 无向图：由没有方向的边构成的图称为无向图。 无向图中的边由顶点的无序偶对组成，因此，在无向图中，顶点偶对vi,vj与顶点偶对vj,vi表示同一条边，记作(vi,vj)。 7.1.1图的定义 有向图：由有方向的边构成的图称为有向图。 弧：有向图中的边由顶点的有序偶对组成。顶点偶对vi,vj表示从顶点vi指向顶点vj的一条有向边，也称为弧。顶点vi是有向边的始点，也称为弧尾。顶点vj是有向边的终点，也称为弧头。 7.1.1图的定义 完全图：含有n个顶点和条边的无向图称为完全图。在完全图中，任意两个顶点之间均有边相连 推论1：具有n个顶点的无向图最多有条边。 有向完全图：含有n个顶点和n(n-1)条弧的有向图称为有向完全图。在有向完全图中，任意两个顶点之间均有两条方向相反的弧。 推论2：具有n个顶点的有向图最多有n(n-1)条弧。 7.1.1图的定义 邻接点：在无向图中，若存在一条边(vi, vj)，则称vi和vj互为邻接点。称边(vi, vj)依附于顶点vi和vj或称边(vi, vj)与顶点vi和vj相关联。 顶点的度：在无向图中，与顶点v相关联的边数称为顶点v的度，记作TD(v)。 在有向图中，顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以顶点v为弧头的弧的数目，记作ID(v)；顶点的出度是指以顶点v为弧尾的弧的数目，记作OD(v)。顶点v的度等于顶点v的入度和出度之和，即TD(v)=ID(v)+OD(v)。 推论3：对于无向图，其总度数是总边数的两倍。 推论4：对于有向图，其总入度、总出度和总边数相等。 7.1.1图的定义 路径：在图G中，从顶点vi出发，经过一系列的边或弧能够到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。该路径上所包含的边的数目称为路径长度 简单路径：若路径上各顶点互不重复，则称这样的路径为简单路径。 环或回路：若路径上第一个顶点和最后一个顶点相同，则称这样的路径为环或回路。 子图：对于图G={V,E}和图G′={V′,E′}，若存在V′ V且E′ E，则称图G′是图G的子图。 7.1.1图的定义 连通图：在无向图中，若从顶点vi到顶点vj有路径存在，则称vi和vj是连通的。如果无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图中的极大连通子图称为该图的连通分量。 推论5：连通图的连通分量就是它本身。 强连通图：在有向图中，若一对顶点vi和vj（vi≠vj）存在从vi到vj和从vj到vi的有向路径，则称vi和vj是连通的。若有向图中任意两个顶点vi和vj（vi≠vj）之间都是连通的，则称该有向图为强连通图。有向图中的极大强连通子图称为强连通分量。 7.1.1图的定义 权：图中边或弧上附带的数据称为权。 网：带权的图称为网。 生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接连通图中所有顶点。 推论6：有n个顶点的连通图，它的生成树一定包含n个顶点和n-1条边。若加上一条边则构成环，若减去一条边则是非连通图。 7.1.2 图的抽象数据类型 7.2 图的存储结构 7.2.1 邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。 设G=(V,E)是一个具有n个顶点的图。它的顶点集合V={v0,v1,…,vn-1}，则顶点间的关系E可用如下形式的矩阵A描述。 对于A中的每一个元素aij满足： 7.2.1 邻接矩阵 【例7-2】对于图7-2（a）所示的无向图，请给出它的邻接矩阵，并根据邻接矩阵计算顶点v2的度。 7.2.1 邻接矩阵 对于带权图（网），邻接矩阵A中的元素定义为： 【例7-4】对于图7-5（b）所示的网，请给出它的邻接矩阵。 7.2.1 邻接矩阵 用C语言描述的邻接矩阵： #define MAXVEX 50 /*最大顶点个数*/ typedef int weight; /*权值*/ typedef struct{ weight arcs[MAXVEX][MAXVEX];/*邻接矩阵*/ DataType data[MAXVEX];/*顶点信息*/ int vexs; /*顶点数*/ }MGraph,*AdjMetrix; 7.2.1 邻接矩阵 2.邻接矩阵的操作 （1）创建邻接矩阵 void C