资源描述：
《C语言数据结构第06讲图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实用数据结构基础第7章图Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.第7章图知识点图的逻辑结构及基本术语邻接矩阵和邻接表的存储结构和特点深度优先搜索和广度优先搜索两种遍历算法图的连通性和生成树的概念最短路径的含义及求最短路径的算法Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLt
2、d.难点图的遍历最小生成树最短路径要求熟练掌握以下内容：图的存储结构图的遍历算法了解以下内容：图的最小生成树和求最小生成树算法带权有向图的最短路径问题Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.第7章目录7-1图的定义和术语7-2图的存储表示7-3图的遍历7-4图的连通性7-5最短路径小结实验7图子系统习题7Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProf
3、ile5.2.0.0.Copyright2004-2011AsposePtyLtd.7-1图的定义和术语图（Graph）是一种比树形结构更复杂的非线性结构。在图形结构中，每个结点都可以有多个直接前驱和多个直接后继。7-1图的定义和术语7-1-1图的定义图（Graph）是由非空的顶点（Vertices）集合和一个描述顶点之间关系——边（Edges）的有限集合组成的一种数据结构。可以用二元组定义为：G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientP
4、rofile5.2.0.0.Copyright2004-2011AsposePtyLtd.图7-1无向图G1图7-2有向图G2V1V3V2V4V5V1V3V2V4G1=（V，E）V＝{v1,v2,v3,v4,v5}；E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称为边。G2=(V,E)V={v1,v2,v3,v4}E={,,,}表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称
5、为弧尾，vj称为弧头。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.7-1-2图的相关术语（1）无向图（Undigraph）在一个图中，如果每条边都没有方向（如图7-1），则称该图为无向图。（2）有向图（Digraph）在一个图中，如果每条边都有方向（如图7-2），则称该图为有向图。（3）无向完全图在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1
6、)/2条边。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.（4）有向完全图在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条弧。（5）稠密图、稀疏图我们称边数很多的图为稠密图；称边数很少的图为稀疏图。（6）顶点的度在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD(v)。Evaluationonly.CreatedwithAspose
7、.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.在有向图中：(a)一个顶点拥有的弧头的数目，称为该顶点的入度，记为ID(v)；(b)一个顶点拥有的弧尾的数目，称为该顶点的出度，记为OD(v)；(c)一个顶点度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。在图7-1的G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图7-2的G2中有：
