数据结构 第七章 图7.1.pptVIP

* * 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性 7.5 有向无环图及其应用 7.6 最短路径 一、 图的定义 图由两个集合V和E构成，记为G=(V,E)，其中V是顶点的有限集合，E是边的有限集合，边是顶点的无序对或有序对。 7.1 图的定义和术语 1.有向图：E中的顶点对是有序的，即每条边都是有方向 的，则称G为有向图。 2.弧：有向图的边v,w，表示从v到w的一条弧。 3.弧头：弧的终点w。 弧尾：弧的起始点v。 4.无向图：E中顶点对是无序的，则称G为无向图。无向图的边用无序对(v,w)表示。 二、图的有关术语 7.1 图的定义和术语 用n表示图中顶点数目，用e表示边或弧的数目。 5.完全图：对于无向图0≤e≤n(n-1)/2,具有n(n-1)/2条边的无向图称为完全图。 6.有向完全图：对于有向图0≤e≤n(n-1)，具有n(n-1)条弧的有向图称为有向完全图。 7.子图：有两个图G=(V,E)和G’=(V’,E’)，如果V’?V且E’?E，则称G’为G的子图。 7.1 图的定义和术语 二、图的有关术语 8.邻接点、关联：对于无向图G=（V，E）,如果边(v,v’) ?E，则称顶点v和v’互为邻接点，即v和v’相邻接。称(v,v’)和顶点v和v’相关联。 9.度：和顶点v相关联的边的数目TD（v）。 10.入度：若G是有向图，则以v为弧头的弧的个数,ID(v)。 11.出度：若G是有向图，则以v为弧尾的弧的个数,OD(v) 12. 路径：无向图从顶点vp到vq的路径是一个顶点序列(vp,v1,v2,…vq-1,vq)，且(vp,v1),(v1,v2)…(vq-1,vq)属于E(G)，其中vp是起点，vq是终点。若是有向图，路径是有向的。 7.1 图的定义和术语 二、图的有关术语 13. 连通(可及)：在图G中，若从顶点v到v’有路径，则称v和v’是连通的(可及的)。 14.连通图：在无向图G中，任意两个顶点都是连通的，称图G是连通图。 15.连通分量：无向图中的极大连通子图。 7.1 图的定义和术语 二、图的有关术语 16.强连通图：在有向图G中，对于任意两个不同顶点vi和vj，vi和vj连通，vj和vi连通，称G为强连通图。 17.强连通分量：有向图中的极大连通子图称作有向图的强连通分量。 7.1 图的定义和术语 二、图的有关术语 18.生成树： 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。 说明：一棵有n个顶点的生成树有且仅有n-1条边； 一个图有n个顶点和小于n-1条边，则是非连通图； 一个图有n个顶点和大于n-1条边，则一定有环。 注：一个图有n个顶点和n-1条边，不一定是生成树， 必须保证连通。 7.1 图的定义和术语 二、图的有关术语 例 2 4 5 1 3 6 G1 顶点2入度： 出度： 度为： 顶点4入度： 出度： 度为： 1 5 7 3 2 4 G2 6 顶点5的度： 顶点2的度： 7.1 图的定义和术语 二、图的有关术语 3 4 1 3 4 1 0 1 例 例 1 5 7 3 2 4 G2 6 例 2 4 5 1 3 6 G1 路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3 路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1 3 5 6 例 2 4 5 1 3 6 图与子图 7.1 图的定义和术语 二、图的有关术语 二、图的有关术语 7.1 图的定义和术语 连通图G1 例 非连通图G2 2 4 5 1 3 6 例 D E I G H K 非连通图G2的三个连通分量 例： 设图G=(V,E)，V={a,b,c,d,e}， E={a,b,a,c,b,d,c,e,d,c,e,d。 回答下列问题： 1.?求与顶点b相关联的弧； 2.?是否存在从顶点c到b的路径？ 3. 求ID(d)、OD(d)、TD(d); 4.?该有向图是否是强连通图？ 5.?画出各个强连通分量。 7.1 图的定义和术语 二、图的有关术语 7.2 图的存储结构 一、邻接矩阵（数组表示法） 二、邻接表 一、邻接矩阵 7.2 图的存储结构 1．方法：定义两个数组