欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    《图论基础算法》PPT课件.ppt

    • 资源ID:71070722       资源大小:238.49KB        全文页数:20页
    • 资源格式: PPT        下载积分:11.9金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要11.9金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    《图论基础算法》PPT课件.ppt

    图论的基础算法DFS与BFS图的存储方式两种n邻接矩阵:n就是用一个矩阵表示一个图,用二维数组来实现mapNNnmapij=1表示i到j有边mapij=0表示不存在边,一般它的实现会在O(n2)的时间复杂度内查边邻接矩阵表示图的存储邻接矩阵n邻接矩阵nmapij表示顶点i和顶点j的边关系n是否有边相连0,1表示n边权值mapij=w;n空间复杂度:O(n2)n访问速度快、直观、适合稠密图的存储方式邻接矩阵n邻接矩阵使用场合n数据规模不大nv=v;np-w=w;np-next=fisrtu;nfirstu=p;n/传说中的挂链遍历图的边n/使用的时候,找u的邻接点nfor(node*p=firstu;p!=NULL;p=p-next)nnintv=p-v;n/在这里作相应的处理n深度优先遍历深度优先遍历(Depth-First Traversal)DFSn深度优先遍历深度优先遍历(Depth-First Traversal)n假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。n图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。对已访问过的点标记操作图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后,又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点,必须记住每个已访问的顶点。为此,可设一布尔向量visited0n-1,其初值为假,一旦访问了顶点Vi之后,便将visitedi置为真。搜索过程n设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。nn#includen#includen#includen#definemaxn107ncharmapmaxnmaxn;/邻接矩阵存图nintvisitmaxnmaxn;/标记节点是否被访问过0表示未被访问过1表示访问过nintdir82=0,1,1,1,-1,0,0,-1,1,0,-1,-1,1,-1,-1,1;n/八个方向nintm,n;nvoiddfs(intx,inty)nninti;nfor(i=0;i=0&tx=0&tyn&!visittxty)nnvisittxty=1;ndfs(tx,ty);nnnnintmain()nn/freopen(d.txt,r,stdin);ninti,j;nwhile(scanf(%d%d,&m,&n)nnif(!m&!n)break;nintcnt=0;nmemset(visit,0,sizeof(visit);nfor(i=0;im;+i)scanf(%s,mapi);n/邻接矩阵的O(n2)找边nfor(i=0;im;+i)nnfor(j=0;jn;+j)nnif(mapij=&!visitij)nnvisitij=1;ncnt+;ndfs(i,j);nnnnprintf(%dn,cnt);nnreturn0;n广度优先遍历广度优先遍历(Breadth-FirstTraversal)n设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点,则广度优先遍历可以定义为:首先访问出发点v,接着依次访问v的所有邻接点w1,w2,wt,然后再依次访问与wl,w2,wt邻接的所有未曾访问过的顶点。依此类推,直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。若G是连通图,则遍历完成;否则,在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程,直至G中所有顶点均已被访问为止。广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索,故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。2、广度优先搜索过程、广度优先搜索过程n在广度优先搜索过程中,设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1,x2,xs和y1,y2,yt。为确保先访问的顶点其邻接点亦先被访问,在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时,这两个顶点相继入队。此后,当x和y相继出队时,我们分别从x和y出发搜索其邻接点x1,x2,xs和y1,y2,yt,对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队,故保证了每个顶点至多只有一次人队。n#includen#includen#includen#definemaxn107nstructnodennintx,y;n;ncharmapmaxnmaxn;/邻接矩阵存图nintvisitmaxnmaxn;/标记节点是否被访问过0表示未被访问过1表示访问过nintdir82=0,1,1,1,-1,0,0,-1,1,0,-1,-1,1,-1,-1,1;nnodeqmaxn*maxn;n/八个方向nintm,n,l,r;nvoidbfs()nninti;nwhile(lr)nnnodept=ql+;/从队列中取出该节点nnodep;nfor(i=0;i=0&p.x=0&p.yn&!visitp.xp.y)/满足条件nnvisitp.xp.y=1;nqr+=p;/入队列nnnnnintmain()nn/freopen(d.txt,r,stdin);ninti,j;nwhile(scanf(%d%d,&m,&n)nnif(!m&!n)break;nintcnt=0;nmemset(visit,0,sizeof(visit);nfor(i=0;im;+i)scanf(%s,mapi);nnodep;nl=r=0;nfor(i=0;im;+i)nnfor(j=0;jn;+j)nnif(mapij=&!visitij)nnp.x=i;p.y=j;nqr+=p;/入队列nvisitij=1;/标记为已经访问过ncnt+;nbfs();nnnnprintf(%dn,cnt);nnreturn0;n

    注意事项

    本文(《图论基础算法》PPT课件.ppt)为本站会员(wuy****n92)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开