Dbettkk-Blog
0%

建图方法总结

Posted on Edited on In Views: Valine:

摘要

本文呢主要想为大家介绍一些常用的建图方法及数据结构，因为大家平时都直接套板子，可能会有一些模糊的地方，希望本文的介绍对大家图论的学习有所帮助。

建图

邻接矩阵

邻接矩阵可以说是最简单最容易理解的建图方法了，简要说就是用一个二维数组存边，下标代表顶点编号。比如map[i][j]即代表顶点i和顶点j之间存在一条边，边的权值为map[i][j]。

1
2
#define max ...
int map[max][max];

这样无论是遍历或者是存边的时候都非常的方便和容易理解。下面用松弛举个遍历的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//存图
int n,m;
int u,v,w;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
    scanf("%d%d%d",&u,&v,&w);
    map[u][v]=w;
    map[v][u]=0;//有向图(无向图为w)
}
//遍历
int tmp;//源点
for(i=1;i<=n;i++){//遍历目标顶点
    if(dis[i]>dis[tmp]+map[tmp][i])//松弛
        dis[i]=dis[tmp]+map[tmp][i];
}

当然也有不可避免的缺点，就是空间占用太大。比如一共10000个点100000条边的时候，就无法用矩阵简单的存储了。只能用其他方法。

邻接表(链式前向星)

链式前向星可以说是一种非常优质的存图结构了，不管是占用内存方面还是遍历方面或者是存边都非常的简单，但有个问题就是不是那么容易理解(反正本人凭自己可能十天八天都不一定弄得明白，还是网上看看博客才懂)。但弄懂了还是很简单的，先放代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define max ...
struct Edge{
    int to;
    int weight;
    int next;
}e[max*max];//max*max代表边总数，实际可能没这么多。
int head[max],e_num=0;
void addedge(int u,int v,int w){
    e[e_num].to=v;
    e[e_num].weight=w;
    e[e_num].next=head[u];
    head[u]=e_num;
    e_num++;
}
void insert(int u,int v,int w){
    addedge(u,v,w);
    addedge(v,u,0);//无向图为w
}
//还要初始化head数组全为-1

上面给大家列出了链式前向星的基本结构以及加边的函数，方便下文阐述。首先拿到这个结构体可能第一次接触的时候有点懵(我第一次直接放弃)，首先to就是指该边指向的顶点，weight就是代表权值了也可以代表容量，然后最神奇的就是next，这个则代表和这条边来自同样起始顶点的下一条边的编号(因为这个结构体数组的下标就是代表边的编号)，然后是head[max]，这个数组存的是边的编号，什么编号呢，以该数组下标为起始顶点的边的编号(该数组的下标即为起始顶点的编号)，并且如果从该起始顶点出发的有多条边，那则代表最后添加进head数组的那条边的编号(好像有点绕)，最后e_num代表的是边的编号也就是e[]的下标。如果没怎么搞明白，不要紧，我们再看看这个加边函数应该就比较清楚了。

首先e_num从0开始，加入第一条边，存其指向的顶点和权值就不多说了，这个比较好理解；然后是e[e_num].next=head[u]，根据我们上文介绍的概念来理解就是，e[e_num].next表示这条边对应的起始顶点的下一条边的编号，等于head[u]，也就等于head数组的初始值-1，因为现在图里只有一条边，所以不存在其他边的情况，所以-1则代表无边。现在图里就一条边，我们假设为顶点1到顶点2有一条边。如下(别忘了同时也相当于加了一条从2->1的权值为0的边，e_num现在为2)

1
2
3
4
5
6
7
//边 1->2
//对应的数组及代码如下
e[0].next=head[1];//head[1]=-1;
head[1]=0;//e_num=0;
//相反的边 2->1 只是权值为0
e[1].next=head[2];//head[2]=-1
head[2]=1;//e_num=1;

然后我们假设再加入一条从1到3的一条边，代码如下

1
2
3
4
5
6
//边 1->3
e[2].next=head[1];//此时head[1]=0
head[1]=2;//e_num=2;
//相反的边
e[3].next=head[3];//head[3]=-1;
head[3]=3;//e_num=3;

然后我们再来分析一下，我们先不看那两条相反的边，只看1->2和1->3这两边。现在head[1]里存的就是边的编号2，也就是最后加进来的起始顶点为1的边1->3。这个点应该清楚了吧。然后是e[2].next这个指的是1->2这条边的编号0，也就是和1->3这条边有相同起始顶点下一条边的编号，也就是1->2这条边的编号，所以是0。然后这些应该清楚了，那为什么要这样设置呢，下面代码则是遍历时的代码，还是举松弛的例子，看完大家应该就理解为什么要这样设置了。

1
2
3
4
5
6
int s;//源点
for(i=head[s];~i;i=e[i].next){
    int v=e[i].to;
    if(dis[v]>dis[s]+e[i].weight)
        dis[v]=dis[s]+e[i].weight;
}

然后我来解释一下这段代码，首先这段代码实现的功能就是对以s源点为起点的所有边进行松弛操作。首先是循环的代码，i就是代表边的编号，初始值就为以s为起点的最后加入head数组的边的编号，~i的意思就是i!=-1了(因为head的初始值我们设为-1)，然后i=e[i].next就代表和当前边具有相同顶点的下一条边的编号了，这样就能遍历以s为起点的所有的边了。然后是v，就是代表当前边的终止顶点，也就是s->v并且编号为i，所以松弛操作就很好理解了，这个循环也就是几乎所有链式前向星实现遍历的循环了。

最后再补充一下为什么有向图要存反向边了，这是为了在解决最大流问题的时候的方便，残余网络等等都需要反向边的参与，这样设置反向边的好处也是很大的，因为就是和其本身这条边编号+1或者准确说是^1就能得到其反向边了。(比如上面例子的边1->2编号为0，2->1编号为1，也就是0^1，对1->3也是同样)所以就很方便。

总结一下就是链式前向星的优势很大，完全不用担心空间的浪费问题，并且其和用单纯的链表存图是异曲同工的，我在这里就不再赘述，缺点就是不那么容易理解，希望大家都能熟练掌握。

vector实现邻接表

用vector实现邻接表就比较简单易懂了，直接放代码。

1
2
3
4
5
6
#define max ...
struct node{
    int v,w;
};
vector<struct node> G[max];//下标为出发点
//vector<pair<int,int> > G[max];

数据结构还是非常的简单易懂的，就是邻接表最朴素的方式，当然熟练后直接使用pair即可，下面放上存边的代码

1
2
3
4
5
struct node e;//临时
scanf("%d%d%d",&u,&v,&w);
e.v=v,e.w=w;
G[u].push_back(e);//和二维数组相似
//G[u].push_back({v,w});

遍历就和二维数组几乎类似了。上代码

1
2
3
4
5
6
7
struct node e;
for(int i=1;i<=n;i++){
    for(int j=1;j<=G[i].size();j++){
        e=G[i][j];
        //e.v,e.w
    }
}

缺点也是有的，比如存在相同边的时候，判断是否重复就比较麻烦了。