资源描述：
《数据结构图结构_(动态PPT).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：1)了解图的定义和术语2)掌握图的各种存储结构3)掌握图的深度优先搜索和广度优先搜索遍历算法4)理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法本章学习导读1图（Graph）是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层
2、的一个结点（即双亲）相关（根结点除外）。然而在图形结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。27.1图的定义7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图3图定义图G由两个集合V和E组成，记为G=(V,E)其中，V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对
3、称为边。通常V(G)和E(G)分别称为图的顶点集合和边集合。注：E(G)可以为空集。7.1图的定义和术语47.1图的定义和术语图的数据结构的形式化定义（p156）G=(V,E)其中V={x
4、xdataobject}E={VR}VR={
5、p(x,y)(x,yV)}VR是两顶点间的关系的集合，即边的集合。5图的术语有向图:对一个图G，若边集E(G)为有向边的集合，则称该图为有向图。①②③④G1G1=（V，E）V={v1,v2,v3,v4}E={,,,}其中<
6、x,y>表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)x弧尾y弧头6图的术语无向图:对一个图G，若边集E(G)为无向边的集合，则称该图为无向图。①②G2③④⑤G2=（V，E）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x与y之间的一条连线，称为边（edge）7图的术语设n为顶点数，e为边或弧的条数对无向图有：0≤e≤n(n-1)/2有向图有：0≤e≤n(n-1)证明：对有向
7、图，每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但对无向图，每条边连接2个顶点，故最多为n(n-1)/28图的术语端点和邻接点在一个无向图中，若存在一条边,则称vi，vj为该边的两个端点，并称它们互为邻结点。21453G29图的术语起点和终点在一个有向图中，若存在一条边,则称该边是顶点vi的一条出边，是vj的一条入边，称vi是起始端点（或起点），称vj是终止端点（或终点）,并称它们互为邻结点.2134G110图的术语度图中每个顶点的度是以该顶点为一端点的边的
8、数目。记为D(V)。入度和出度对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的数目。例D(v1)=3无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v为弧头的弧数与以顶点v为弧尾的弧数之和21453G22134G1例D(v1)=211图的术语子图设有两个图G=（V，E）G’=（V’，E’）中，若V’是V的子集，E’是E的子集，则称G’是G子图。①①④①③④⑤①②③④⑤①②G2③④⑤12图的术语简单图对不含多重边和自环的图。2145321453简单图非简单图13图的术语完全图边达到最大的图无向完全
9、图：具有n(n-1)/2条边的简单图称为无向完全图有向完全图：具有n(n-1)条边的有向图。稀疏图：边或弧很少的图。稠密图：边或弧很多的图。权：与图的边或弧相关的数。网：边或弧上带有权值的图。14图的术语路径非空有限点、弧交替序列，W=v0,a1,v1,…,ak,vk使得i=1,2,…k,弧ai的头vi,尾为vi-1。路径长度：路径上边或弧的数目15图的术语简单路径：除首尾两点外，其他各点都不相同的路径称为简单路径。简单路径16图的术语回路:无重复边的闭路径。环：闭的简单路径，称为环。回路但不是环环17图的术语连通图：任何两
10、点都有路径的图。无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vi<>vj)有向图：若图中任意两个顶点vi,vj，都存在 从vi到vj和从vj到vi的路径，则称该有向图为强连通图(vi<>vj)18图的术语连通分量：无向图：无向图中极大连通子图，称为 连通分量有向图：有
