清华大学与朱明方数据结构5 .ppt

第五章 图 5.1 图的基本概念 一. 图的定义 二. 顶点的度 三. 路径与连通 5.2 图的存储结构 一. 邻接矩阵 二. 邻接表 三. 边集数组 四. 邻接多重表 5.3 图的遍历 一. 深度优先遍历 二. 广度优先遍历 5.4 最短距离问题 5.1 图的基本概念 一. 图的定义 图—图形结构简称。允许集合中的元素间有任意前后件关系。 即数据元素间是多对多的联系。每个元素构成一个顶点。 图的二元组定义为： G=( V, E ) V—顶点集合， E—V上的一个二元关系。 例如，图： G1= ( V(G1), E(G1) ) V(G1)= { A, B, C } E(G1)= { ?A, B?, ?A, C?, ?B, C?, ?C, B? } 每个序偶对应一条有向边 (带箭头的边) G2= ( V(G2), E(G2) ) V(G2)= { v1, v2, v3 } E(G2)= { (v1, v2), (v1, v3), (v2, v3) } 每个无序对对应一条无向边(无箭头的边) 5.1 图的基本概念 一. 图的定义 E(G1)、E(G2)可以看成是边(有向边或无向边)的集合。 根据图的二元组定义，G=( V, E ) 有： 图——由顶点集合V和边集合E组成。 图G1中的边为有向边——有向图。 图G2中的边为无向边——无向图。 若图G ′ =(V′,E′)与图G=(V, E)满足： V(G ′) ? V(G), E(G ′) ? E(G) 则称G ′为G的子图。 例如，图G： 图G ′： G ′为G的子图 5.1 图的基本概念 二. 顶点的度 无向图：边—(Vi,Vj)， 端点—Vi, Vj—互为邻接点。 顶点的度—顶点连接的边数D(Vi)， 若图中每两个顶点间都有边—完全图—边数为最大值n(n-1)/2 。 有向图：边——?Vi,Vj?——Vi的出边、Vj的入边； 起点—Vi—Vj的入边邻接点； 终点—Vj—Vi的出边邻接点。 顶点入度——顶点连接的入边数；D-(Vi) 顶点出度——顶点连接的出边数；D+(Vi) 顶点的度=顶点入度+顶点出度。 设顶点i的度为D(Vi)，图中有n个顶点,则其边数m为： m= ——握手定理。 推论：图中度为奇数的顶点有偶数个。 5.1 图的基本概念 三. 路径与连通 无向图，若存在边：(vp,vi1)，(vi1,vi2)，…，(vin-1,vin)，(vin,vq)， 有向图，若存在边：?vp,vi1?,? vi1,vi2 ? , …,? vin-1,vin ? ,? vin,vq ?，则： 顶点序列(vp,vi1 ，…，vin,vq)为vp到vq的一条路经。 路径长度——路径上所有边的数目。 顶点vi到vj有路径——vi到vj连通。 无向图中，任意两顶点都连通——连通图。 极大的连通子图——连通分量。 有向图中，任意两顶点都连通——强连通图。 极大的强连通子图——强连通分量。 (c)强连通图 (d)强连通分量 5.1 图的基本概念 三. 路径与连通 实际问题中抽象出来的图，图中每条边上可以标有具体 意义的