高中信息竞赛-数据结构—图基本概念及搜索遍历.ppt

该【高中信息竞赛-数据结构—图基本概念及搜索遍历 】是由【相惜】上传分享，文档一共【30】页，该文档可以免费在线阅读，需要了解更多关于【高中信息竞赛-数据结构—图基本概念及搜索遍历 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。,那么此数据结构G=(D,R)称为图。奥林匹克信息学联赛的许多试题,需要用图来描述数据元素间的联系,需要用图的经典算法来解题,例如:用结点代表城市,每条边代表连接两个城市间的公路,边长的权表示公路长度。这种公路网的表现形式就是属于图的数据结构。.图的根本概念图的的定义如果数据元素集合D中的各元素之间存在任意的前后件关系R,那么此数据结构G=〔D,R〕称为图。如果将数据元素抽象为结点,元素之间的前后件关系用边表示,那么图亦可以表示为G=〔V,E〕,其中V是结点的有穷〔非空〕集合,E为边的集合。如果元素a是元素b的前件,这种前后件关系对应的边用(a,b)表示,即(a,b)∈E。.无向图和有向图⑴无向图:在图G=〔V,E〕中,如果对于任意的a,b∈V,当(a,b)∈E时,必有〔b,a〕∈E〔即关系R对称〕,对称此图为无向图。在一无向图中用不带箭头的边连接两个有关联的结点。在具有n个结点的无向图中,边的最大数目为n*(n-1)/2。而边数到达最大值的图称为无向完全图。在无向图中一个结点相连的边数称为该结点的度,无向完全图中,每一个顶点的度为n-1。无向完全图。结点1、结点2、结点3、结点4的度分别为3.⑵有向图:如果对于任意的a,b∈V,当(a,b)∈E时,(b,a)∈E未必成立,那么称此图为有向图。在有向图中,通常用带箭头的边连接两个有关联的结点(方向由前件指向后件)。有向图中一个结点的后件个数称为该结点的出度,其前件个数称为该结点的入度。有向图结点1的出度和入度分别为1,=〔V,E〕中,如果对于结点a,b,存在满足下述条件的结点序列x1……xk(k>1)⑴x1=a,xk=b⑵(xi,xi+1)∈Ei=1‥k-1那么称结点序列x1=a,x2,…,xk=b为结点a到结点b的一条路径,而路径上边的数目k-1称为该路径的长度,并称结点集合{x1,…,xk}为连通集。x1=ax2…xk=,其它结点均不相同,那么称此路径为一条简单路径。x1=xk的简单路径称为回路〔也称为环〕。v1→v2→v3是一条简单路径,v1→v3→v4→v1→v3不是简单路径v1→v2→,假设存在一个结点w,它与其他结点都是连通的,那么称此图为有根图,结点w即为它的根。有根图,v1、v2、v3、v4都可以作为根有根图,v1或v2为它的根。.连通图和最大连通子图对于无向图而言,假设其中任两个结点之间的连通,那么称该图为连通图。一个无向图的连通分支定义为此图的最大连通子图。上图所示的图是连通的,它的最大连通子图即为其本身。.强连通图和强连通分支假设对于有向图的任意两个结点vi、vj间〔vi≠vj〕,都有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,那么称该有向图是强连通的。有向图中强连通的最大子图称为该图的强连通分支。上图不是强连通的,.