前言:
本节课讲的是图论的几种遍历方式,若没看图论初步1的赶紧去看
https://www.cnblogs.com/Craker/p/12271090.html
正文:
零、温故而知新
上节课我们学的是图论最最最基础的邻接矩阵和邻接表(哎呀,邻接矩阵那么简单这里还复习个啥啊)
邻接表的“插队”模板还记得吗?温习一下,再打一遍(巨佬石老师提醒您:这都不会打,给我痛扁一顿)
void add(int x,int y,){ ++tot; e[tot].u=x; e[tot].v=y; e[tot].next=head[x]; head[x]=tot; }
别忘了哈
一、深度优先遍历
(1)邻接矩阵(大佬kkksc03:这么弱智的你也写)
没啥好说的,几个要点:
1、与深搜基本没啥区别(其实深搜是图论的一个分支)
2、(看看标准的是怎么说的)
主要意思:沿一个点搜下去,标记已搜的,若 “无路可走”则返回到上一个点
代码:
void dfs(int v) { cout<<v<<" "; visited[v]=;//标记 ;j<=n;j++){ &&g[v][j]== )dfs(j);//搜下去 } //由于 我们只是遍历一下所以不用回溯 }
(2)邻接表:(哎呀,大同小异啊)
代码:
void dfs(int v){ visited[v]=; //标记 cout<<v<<" "; ;i=e[i].next){ ){ dfs(e[i].v); } } }
二、广度优先遍历
这是一种很像“层式遍历的东西”,不过本人却不太喜欢
(1)、邻接表(唉,邻接矩阵就不讲了喽大佬kkksc03:强烈支持!)
咋写呢? 队列来了!
何为队列?画一张丑陋的图
贴代码吧:
void bfs(int u){ ,t=; ]; a[t]=u;//入队 b[u]=; //标记下一 while(h<t){ //咦?为啥是小于而不是等于呢?自己想 h++; //还是说吧:如果是小于等于的话head岂不大于tail了? int v=a[h]; cout<<v<<" "; //输出 ;i=e[i].next){ int x=e[i].v; ){ //不在队吧 b[x]=; //标记 ++t; a[t]=x; //入队 } } } }
某大佬可能会说:这种队列也太土了吧? 本人表示:越土的东西越好用 反正指针我是不学的
写在后面的话:
这是我的第二篇博客(bug一定很多)(如有锅请赶快在评论区指出,谢谢!)
本人的个人主页(洛谷)https://www.luogu.com.cn/user/236929
本人的个人主页https://www.cnblogs.com/Craker/
欢迎来访!
谢谢!
本人QQ:2783119105
本人邮箱:yixuazeng66@126.com
如有问题,请在评论区指出或私信我,
谢谢!
(点个赞再走呗)(管理员kkksc03温馨提醒您:刷不到赞莫强求)