图论初步<蒟蒻专属文章>

2020-02-08 16:01:06来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

图论初步<蒟蒻专属文章>

前言:    图论乃noip之重要知识点,但有点难理解 本人因此吃过不少亏

     因为本人实在太弱,所以此篇乃正宗<蒟蒻专属文章>

正文:(本文仅介绍图论中的重点、难点,其余部分略将或不讲)

   

       图一般来说有二种存储方法:邻接矩阵和邻接表

邻接矩阵

      存储:拿二维数组来存
  

for(int i=1;i<=n;++i){   //f[q][z]表示点q与点z有没有边相连接
    cin>>q>>z;  //noip基本别指望,最多三四十分
    f[q][z]=1;  //无向边要存双向 
    f[z][q]=1;
} 

       可是,虽然存储简单,可效率也太低了(尤其是些超级稀疏的矩阵)

  而且,坏处还没完:读取效率也很低!

       读取:

  

cin>>x;//读入x,查与x有关的点 
for(int i=1;i<=n;++i){  //据说++i比i++快一些 
    if(f[x][i]==1){
        cout<<i<<" ";
    } 
} 

 这么暴力的for循环,不超时才怪呢

  所以,另一种办法来了:邻接表!!

 原理:

     通过链表的形式,高效的存储/读取边

先使用struct:(我太蒻,只会用struct存)

struct node{
           int u,v,next;//u起点,v终点,next待会在说 啥意思 
   }e[MAXN*2]; //无向图要*2(原因:要存两次)!!!!有向图似乎只要一倍 
   //这类数组名都用e,养成好习惯 

 

读取:

for(int i=1;i<=n;++i){
       cin>>q>>z;  //这类函数名名都用e,养成好习惯 
       add(q,z);  //无向边要存双向 
       add(z,q);  //通常 用自定义函数实现 
   }

add(加边函数):    注意:要定义head数组,表示点i当前的第一个连接的数组下标!!!!!

 

代码:

void add(int x,int y,){
   ++tot;
   e[tot].u=x;
   e[tot].v=y;
   e[tot].next=head[x]; 
   head[x]=tot;
}

一些question&Answer&注意事项:

1:为什么偏偏要插队?

Answer:因为如果不插队,将要加的边就没法指向上一个了(难道你还for一遍?);

2:链表结构其实还有很多其余的办法实现,但我写的这种更适合初学者

(emm.....好像就两个也)

 “遍历”方式:

cin>>a; //问和a号点相邻的边有哪些
    for(int i=head[a];i!=0;i=e[i].next){  //从点a的第一条边开始,若为0结束 
        cout<<e[i].u<<" "<<e[i].v<<endl;   // 到下一个数组下标 
    } 

(完)

写在后面的话:

     这是我的第一篇博客(bug一定很多

  本人的个人主页(洛谷)https://www.luogu.com.cn/user/236929  

    本人的个人主页https://www.cnblogs.com/Craker/

欢迎来访!

谢谢!

本人QQ:2783119105

本人邮箱:yixuazeng66@126.com

如有问题,请在评论区指出或私信我,

谢谢!

 


原文链接:https://www.cnblogs.com/Craker/p/12271090.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:AtCoder agc007_d Shik and Game

下一篇:Asteroids!_poj2225