资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
赛前知识点梳理_数据结构一)基本概念线性表:数据间关系是线性的,每个元素只有一个前趋,一个后续;树:有着明显的层次关系,每个元素只有一个前趋,但有多个后续;图:数据之间的关系是任意,每个元素的前趋和后续个数是不定的;引入:柯尼斯堡七桥问题,能否从A地发出,各座桥恰好通过一次,最后回到出发地A?画问题”。答案是否定的,因为,对于每一个顶点,不论如何经过,必须有一条进路和一条岀路,与每一 个顶点相邻的线(关联边)必须是偶数条(除起点和终点外),而此图中所有点都只有奇数条关联边。在 后面的应用中,我们将专门讨论这个问题。定义:简单讲,一个图是由一些点和这些点之间的连线组成的。严格意义讲,图是一种数据结构,定 义为:graph= (V,E)。V是一个非空有限集合,代表顶点(结点),E代表边的集合,一般用(Vx, Vy) 表示,其中,Vx, Vy属于V。分类:如果边是没有方向的,称为“无向图”。表示时用一队圆括号表示,如:(Vx, Vy),(Vy, Vx),当然这两者是等价的。并且说边(Vx,Vy)依附于(相关联)顶点Vx和Vy。如果边是带箭头的, 则称为“有向图”,表示时用一队尖括号表示,此时Vx, Vy与VY, VX是不同的,如VX, VY的起点为 VX,终点为VY。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。PVy, Vx是不同的,如Vx, Vy的起点为Vx,终点为Vy。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。相邻:若两个结点 U、 V 之间有一条边连接,则称这两个结点 U、 V 是关联的。带权图:两点间不仅有连接关系,还标明了数量关系(距离、费用、时间等)。 图的阶:图中结点的个数。结点的度:图中与结点A关联的边的数目,称为结点A的度。入度:在有向图中,把以结点V为终点 的边的数目称为V的入度;出度:在有向图中,把以结点U为起点的边的数目称为U的出度;奇点:度数为奇数的结点; 偶点:度数为偶数的结点; 终端结点:在有向图中,出度为0的结点;定理1:图中所有结点的度数之和等于边数的2倍:定理2:任意一个图一定有偶数个奇点:连通:如果图中结点U, V之间存在一条从U通过若干条边、点到达V的通路,则称U、V是连通的。路(径):从一个结点出发,沿着某些边连续地移动而到达另一个指定的结点,这种依次由结点和边 组成的序列,叫“路”或者“路径”。路径长度:路径上边的数目。简单路径:在一个路径上,各个结点 都不相同,则称为简单路径。回路:起点和终点相同的路径,称为回路,或“环”。连通图:对于图G中的任一对不同顶点U、V,都有一条(U, V)通路,则称图G是连通的。强连通图:在有向图G中,每一对结点之间都有路径的图。网络:带权的连通图。二)表示方法巾 UR1、邻接矩阵表示法(顺序存储)72CO 5C O匸:口 |匚:口1 15 g 1. g 2 请大家自己画出图(C)如上图(B)和10的邻接袒阵分别如下:A =的邻接表分别如下,0 1 12、接表表示法(链式存储法)A)、图(B)nilnil3ml无向图:AI, J = 1当I与J两个结点相邻时= 0 当 I 与 J 两个结点不相邻时,或 I=J(1=I, J=图中结点数)且有:AI,J=AJ, I,即邻接矩阵是对称的。 如上图(A)的邻接矩阵如下:当I与J两个结点相邻,磁值为PI,J时当I与J两个结点不相邻时,或I=J(三)图的遍历1、概念:从图中某一结点出发系统地访问图中所有结点,使每个结点恰好被访问一次,这种运算称 图的遍历。为了避免重复访问某个结点,可以设一个标志数组visitedI,未访问时值为FALSE,访问一 次后就改为 TRUE。2、分类:深度优先遍历和广度优先遍历。3、深度优先遍历:类似于树的先序遍历,从图中某个结点V0出发,访问此结点,然后依次访问从V0 的未被访问的邻接点出发进行深度优先遍历,直到图中所有和V0有路径相通的结点均被访问到。若此时 图中尚有结点未被访问,则另选图中一个未被访问的结点V1作为起点,重复上述过程,直至图中所有结 点都被访问到为止。 如下面两个图的深度优先遍历结果分别为:a, b, c, d, e, g, fV1, V2, V4, V8, V5, V3, V6, V7的所有结点,然后再分别从这些结点出发进行广度优先遍历,直到图中所有被访问过的结点的相邻结点都被访问到。若此时图中还有结点尚未被访问,则另选图中一个未被访问过的结点作为起点,重复上述过程直到图中所有结点都被访问到为止。如上面两个图的广度优先遍历结果分别为:a,b,d,e,f,c,gV1,V2,V3,V4,V5,V6,V7,V8 (四)最小生成树问题如果图G=(V, E)是一个连通的无向图,则从G的任一个顶点出发进行一次深度优先遍历或广度优先 遍历便可遍历全部图。设遍历过程中走过的边的集合为TE(G),显然T=(V,TE)是G的一个连通子图,且T本身也是一 棵树(无根树),则称T是G的生成树。1210上图(B)和(C)是对(A)分别进行深度和广度优先遍历得到的一种生成树。注意,图的生成树是10从顶点了出发姑舍不唯一的。对于一棵带权树,生成树中各边的权值之和称为这棵生成树的代价,代价最小的生成树称为“最 小代价生成树”。如何求最小代价生成树呢? R.C.Prim提出的求最小代价生成算法是常用的一种,设图的顶点集合V共 有 n 个顶点,则算法如下:1、设置一个顶点的集合S1和一个边的集合TE,S1和TE的初始状态均为空集;2、选定图中的一个顶点K,从K开始生成最小代价生成树,将K加入到集合S1;3、重复下列操作,直到选取了 n-1条边:选取一条权值最小的边(X, Y),其中XUS1, not(YuSl)。将顶点Y加入集合S1,边(X, Y)加入集合TE。下图给出了上图(A)的最小代价生成树的生成过程:(五)一笔画问题 请你设计一个程序,对给定的一个图,由计算机判断能否一笔画出,若能请打印出一笔画的先后顺序若不能则打印“NO SOLUTION!”。1. 欧拉路:在无孤立结点的图G中,若存在一条路,经过图中每条边一次且仅一次,则称此路为 欧拉路。如下图(左)可以构成一个欧拉路2. 欧拉回路:若存在一条路,经过图中每条边一次且仅一次,且回到原来位置,则称此路为欧拉 回路。因此,七桥问题转换成了欧拉回路问题。如下图(右)可以构成一个欧拉路3. 欧拉图:存在欧拉回路的图,称为欧拉图。4. 定理1:存在欧拉路的条件:图是连通的,且存在0 个或2个奇点。5. 定理2:存在欧拉回路的条件:图是连通的,且存在0个奇点。6. 哈密尔顿图:无孤立结点的连通图,若存在一条路,经过图中每一个结点一次且仅一次,则称 为哈密尔顿图。7. 哈密尔顿环:是一条沿着图的n边环行的路径,它访问每一个结点一次且仅一次,并且返回到 它的开始位置。(七)拓扑排序问题 一项大的工程可以看作是由若干个称为“活动”的子工程组成的集合,这些子工程之间必定存在一种 先后关系,即某些子工程必须在其它一些工程完成之后才能开始,我们可以用有向图表示工程间关系,子 工程(活动)为顶点,活动之间的先后关系为有向边,这种有向图称为顶点表示活动的网络,又称为AOV 网。在AOV网中,如果有一条从顶点Vi到Vj的路径,则说Vi是Vj的前趋,Vj是Vi的后续。如果有弧 Vi, Vj,则称Vi是Vj的直接前趋,Vj是Vi的直接后续。VI, VJ,则称VI是VJ的直接前趋,VJ是 VI的直接后续。拓扑排序是把AOV网中所有顶点排成一个线性序列(拓扑序列),如果有弧Vi,Vj,则 序列中顶点 Vi 在 Vj 之前。一个存在回路的有向图顶点是不能排成拓扑序列的,因为有回路的有向图的边 体现的先后关系不是非自反的。任何没有回路的有向图,其顶点都可以排成一个拓扑序列。而且得到的拓 扑序列是不唯一的。如对下图进行拓扑排序可以得到多个拓扑序列,如: 02143567、01243657、02143657、 01243567。 在这个AOV网络之中,工程1和过程2显然可以同时进行,先后无所谓。但工程4显然要等工程1和 工程 2 都完成以后才可进行,工程3要等到工程 4 完成以后才可进行(当然工程1 也要完成后,显然), 工程 5、又要等到工程3完成以后(工程4 也必须先完成,显然),工程6则要等到工程 4 完成后进行, 工程 7要等到工程 3、5、6 都完成后才能进行。(八)关键路径问题利用AOV网络,对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一 定的时间,为了能估算出某个活动的开始时间,找出那些影响工程完成时间的最主要的活动,我们可以利 用带权的有向网,图中的顶点表示一个活动结束(开始)的事件,图中的边表示活动,边上的权表示完成 该活动所需要的时间。这种用边表示活动的网络,称为AOE网络。下图表示一个具有12个活动的AOE网络。图中有8个顶点,分别表示事件(状态)0到7,其中,0 表示开始状态, 7表示结束状态;边上的权表示完成该活动所需要的时间。在实际中, AOE 网络没有回路,存在唯一的入度为 0 的开始顶点,存在唯一的出度为 0 的结束顶点。 在 AOE 网络上,要研究的问题是完成整个工程至少需要多少时间,哪些活动是影响工程进度的关键。在 AOE 网络中,有些活动可以并行地进行,所以,完成工程的最少时间是从开始顶点到结束顶点的最 长路径的长度。关键路径就是指从开始结点到完成结点的具有最大长度的路径。关键路径上的活动称为关键活动。关 键路径的长度就是完成整个工程所需要的最短时间。(十)图的综合应用举例11999 年初赛试题高中组第二大题题目将ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如,当n=1时,11=2。进 一步考虑,用n条折成角的直线(角度任意),放在平面上,能确定的最大区域数目zn是多少?例如, 当 n=1 时,z1=2。 分析1、第n条直线与前n-1条直线最多有n-1个交点,它们将第n条直线分割成n段,每一段都不在同 一个区域内,且将其所在区域一分为二,即多出n个区域。也就是说L=Ln-1+n,nL =L +nn n-1L =L +n-1n-1n-2L = +22 L1L =L +110L =10将等式左边和右边分别相加得:L =(n+1)*n/2+1n2、将第n条折线当作两条射线来考虑,每条射线与前2*(n-1)条射线最多有2*(n-1)个交点,它们将 每条射线分割成2n-1段,从而多出2*(2n-1)个区域,由于是折线,连接折线交点的两段线段是处于同一 区域内的,因而要少算一个区域,即只多出4*n-3个区域。也就是说:Z =Z +4n-3,同样地n n-1Z =Z +4(n-1)-3n-1n-2Z =Z +4*2-3Z =Z +4*1-310Z =10将等式左边和右边分别相加得:Z =4*(n+l)*n/2+l-3*n=2n2-n+ln2求关键路径(2001 年初赛)问题描述设有一个工程网络如下图表示(无环路的有向图):其中,顶点表示活动,表示工程开始,表示工 程结束(可变,用N表示),边上的数字表示活动延续的时间。编程求关键路径。32001 年初赛问题描述设在A、B两个城市之间有N个路站(如下图中的S1,且N10
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号