数据结构(第二版)课件 包振宇 第六章 图.ppt

《数据结构(第二版)课件 包振宇 第六章 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章图本章内容6.1图的定义与术语6.2图的存储结构6.3图的遍历6.4最小代价生成树6.5*求最短路径6.6拓扑排序6.7拓扑排序6.1图的定义与术语6.1.1定义：1、图G由两个集合V和E组成，记作G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常V（G）和E(G)分别表示G的顶点的集合边的集合，E（G）也可以为空集，若E（G）为空，则图G只有点而没有边。2、在图G中，如果代表边的顶点偶对是无序的，则称G为无向图。把无向图中代表边的无序对用括号括起来，用

2、以表示一条无向边，例（Vi,Vj）表示顶点Vi,Vj的一条无向边，显然（Vi,Vj）和（Vj,Vi）所代表的是同一条边。3、若图G中表示边的顶点偶对是有序的，则称G为有向图。有向图中的边又称为弧，用一对尖括把有序偶对括起来，表示一条有向边，例：表示从顶点Vi到Vj的一条弧，顶点Vi称为的尾,Vj为的头，用由尾指向头的箭头形象表示一条弧。可见和是两条不同的弧。例6.1一个简单无向图其顶点集合与边集合如下：V（G1）={V1，V2，V3，

3、V4}E（G1）={（V1，V2），（V1，V3），（V1，V4），（V2，V3），（V3，V4）}则图例为图6-1。例6.2例6.2：有一有向图其顶点集合与边集合如下：V（G2）={V1，V2，V3，V4}E（G2）={,,,,}V4V1V2V3则图例为图6-2。6.1.2术语1、稀疏图与稠密图具有n个顶点的无向图，边的最大数目是n(n-1)/2，有n(n-1)/2条边的无向图，称为无向完全图（如图6-3）。与之对应的有向完全图，则

4、有n(n-1)条边（如图6-4）。n(n-1)是n个顶点的有向图的最大边数，在n个顶点的图中，当边数e

5、1v1v2v2v3v3v4v4v1术语（续）4、邻接点：在图G中，若（Vi，Vj）是E（G）中的一条边，则称顶点Vi和Vj是互为邻接点。例上图G中V1,V2互为邻接点。5、路径与回路在图G中，顶点Vp到顶点Vq的一条路径是顶点序列（Vp，Vi1,Vi2,…Vin,Vq）,且（Vp,Vi1）,(Vi1,Vi2),…(Vin,Vq)属于E（G）。如果G是有向图，则路径也是有向的，由E（G）中的边,,…组成，路径的长度是指在这条路径上边的数目。在一条路径中，除

6、了第一顶点和最后一顶点之外，其它顶点都不同的路径，称为简单路径。第一顶点与最后一顶点相同的简单路径，称为回路或环。术语（续）6、连通图和强连通图在无向图中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若V（G）中每一对不同顶点Vi和Vj都连通，则称G是连通图，在无向图中，极大的连通子图，称为它的连通分量。在有向图中，若对于V（G）中的每一对不同顶点Vi,Vj都存在以Vi到Vj以及Vj到Vi的路径，则称图G是强连通图，有向图中极大的强连通子图称为它的强连通分量。示例连通分量强连通AV1BV2CV3DEF

7、HGILJK术语（续）7、生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的n-1条边，如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有第二条路径。一棵有n个顶点的生成树有且仅有n-1条边，如果一个有n个顶点和小于n-1条边则是非连通图，如果它多于n-1条边，如果它多于n-1条边，则一定有环。注意有n-1条边的图不一定是生成树。8、度、入度和出度在无向图中，顶点的具有的边的数目称该顶点的度，在有向图中以某顶点为头（终点）的边的数目，称为

8、该顶点的入度以某顶点为尾（始点）的边的数目，称为该顶点的出度。一个顶点的入度与出度之和为该顶点的度。假设无向图G中有n个顶点，e条边，每个顶点的度为di（1≤i≤n），则e=。例6-4例6-5例6.5:图6-11中A的度为：4;图6-13中V4的入度为：2，V4的出度为1,V4的度为：3。6.2图的存储结构6.2.1邻接矩阵图的邻接矩阵是反映顶点间邻接关系的矩阵，设G=（V，E），是具有n(n≥1)个顶点的图，G的邻接矩阵M是一个n列的矩阵