图的存储

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

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

图论的基础就是存图了，存图用的多的貌似也就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(n²)

　　访问

　　　　如果要访问从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]，为当前边的标号，不断判断e[now].to是否为v，若不是则now=e[now].next

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

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

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

 

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

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