图的存储

2019-02-20 00:43:33来源:博客园 阅读 ()

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

新人第一篇文章,做的很烂……

图片不知道怎么搞就不搞了吧

图论的基础就是存图了,存图用的多的貌似也就2种,邻接矩阵和邻接表(貌似邻接表又叫前向星来着

1、邻接矩阵

  邻接矩阵不适用于顶点数较多的图(MLE……

  不过对于数据水一点的题还是蛮方便蛮好用的

  建图

    首先建立一个N*N的二维数组map,N为顶点数

    对于有向图,读入一条由x至y的边,就map[x][y]=1,表示有一条从顶点x到顶点y的边

    如果是带权图呢?那就把1改成边权就行了

    对于无向图……就map[x][y]=map[y][x]=1,因为无向图可以看成点与点有2条边的有向图

    然后就和有向图一样啦

    可以看出空间复杂度为O(N2)

  访问

    如果要访问从x到y的边,只需访问map[x][y]就行了

    不为初始值就说明有边,边权为map[x][y]的值

    时间复杂度为O(1)

    顶点u的入度为map[i][u](i=1 to N)不为初始值的个数,因为map[i][u]代表从i到u的边,这条边以顶点u为终点

    顶点的出度也同理,为map[u][i](i=1 to N)不为初始值的个数,因为map[u][i]代表从u到i的边,这条边以顶点u为起点

2、邻接表

  邻接表我就只会链式前向星嘤嘤嘤

  那就只说链式前向星吧(也好用

  建图

    与邻接矩阵存每个点的情况不同,链式前向星是以存边为基础的

    一条边有终点、起点、权这些属性,所以可以用结构体存储

    但是不能就这样存图,起点是不需要的,因为链式前向星是以一个顶点开始,遍历以该点为起点的所有边,自然地在遍历时就已经知道起点是什么了

    然而要遍历以一个点为起点的所有边,怎么去访问下一个呢?

    给边标号,就这样

    把边的数组的下标作为边的标号,在结构体内加一个next表示接下来该访问哪条边,next的值为下一条边的数组下标

    所以结构体可以这样建立

struct Edge
{
    int next;
    int to;
    int val;
}e[10005];

    to代表这条边的终点,val为边权

    那么怎么样知道一个顶点出发的第一条边的标号呢?

    再开一个head数组,存这个顶点出发的第一条边的标号,根据存好的边内的next,就可以遍历以这个顶点为起点的所有边了

    那么建图的时候,先搞一个cnt变量,代表当前读入边的标号,读入一条从u到v,边权为w的边,就把e[cnt].next的值改为head[u],head[u]的值改为cnt,e[cnt].to的值改为v,再把cnt++,就完成了一条边的读入,相当于是在顶点和之前的第一条边中间插进去了一条边,所以原来的第一条边就变成了第二条,新进去的边就变成了第一条

    cnt也可以直接用循环内的i来代替,head数组需赋初值,为了遍历时判断有无剩余的边,也可以说,如果访问时有个next是初值,那么就到头了,没边了;如果head[u]为初始值,那么就说明没有u出发的边

    下面上图

    

    这个一个顶点u,当前它没有边,head[u]=-1

  

    现在新插进去一条边,原来是没有边的,图上e[1]应为e[1].next,边1为最后一条边,所以e[1].next=head[u],为初始值,而同时边1也是第一条边(因为只有一条边),所以head[u]的值会更新为边1的标号

    

    现在有条标号为2的边也想进去,那么它就要把边1挤开,自己去做第一个,让边1做第二个

  

    边2进去了,边1被赶走了,变成了第二条,所以边2的下一条边就是边1了,e[2].next=head[u],而边2变成第一个了,所以记录第一条边的head[u]会更新为边2的标号

    如果还要加边,同理

    可以得到代码为

for(int i=0;i<n;i++) //n为输入的边数
{
    int x,y,w;
    cin>>x>>y>>w;
    e[i].to=y;
    e[i].next=head[x];
    e[i].val=w;
    head[x]=i;
}

    无向图加2次边即可,起点终点反一下

    于是就完成了建图

  访问

    存图时是存了一个顶点的所有边,所以如果要访问从u到v的边,就要设一个now=head[u],为当前边的标号,不断更新now为e[now].next,判断e[now].to是否为v,若是则为要访问的边

    如果now=-1,那么就说明当前是最后一条边了,后面就没了,于是跳出循环

    无向图由于存边时存了2次,所以与有向图一样就行了

int now=head[u];
while(now!=-1)
{
    if(e[now].to==v)
    {
        /*
            ..........
        */
    }
    now=e[now].next
}

 

萌新第一次写东西,如果有什么可以改进的地方就评论一下吧

评论来一个好吗?秋梨膏!

  

 

 

    

 


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

标签:

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

上一篇:30.C++复习篇

下一篇:Luogu P2590 [ZJOI2008]树的统计