图论初步2<蒟蒻专属,大佬勿喷>

时间:2021-10-18 12:10:14

前言:

本节课讲的是图论的几种遍历方式,若没看图论初步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、(看看标准的是怎么说的)图论初步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:强烈支持!)

咋写呢? 队列来了!

何为队列?画一张丑陋的图

图论初步2<蒟蒻专属,大佬勿喷>

贴代码吧:

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温馨提醒您:刷不到赞莫强求)