存图方法
几种ACM常见的存图方式:
1.邻接矩阵:
我之前一直在用的就是邻接矩阵,非常简单,不过占用空间比较多,另外遍历时间比较长,因此不推荐。
2.vector实现邻接表:
1 | struct node |
3.链式前向星,这也是最重要、最高效的存图方式。稍微有点难理解。
首先,链式前向星由一个结构体edge[]
、数组head[]
组成
edge[]数组
:首先是记录u,v,w这三个基本信息,还有链式前向星的灵魂之一:next
1
2
3
4
5struct node
{
int u, v, w, next;
//起点,终点,边权,next为要遍历的下一条边的编号
} edge[M];head[]数组
:head[i]记录输入的以i为起点的最后一条边的编号
我们先模拟一遍最简单的情况,看看链式前向星是如何做到快速访问所有同一起点的所有边的。假设输入三条边,这三条边的信息如下:
1 | 3 |
按照代码,模拟之后,我们可以得到下图:
这样建立好关系之后,怎么快速遍历所有以1为起点的边呢?上面已经提到head[i]
记录的是以i为起点的最后一条边的编号,因此,我们显然可以从head[1]
开始遍历,那么以1为起点的倒数第二条边的编号是多少呢?这就要用到next
了,是edge[head[1]].next。当edge[i].next为0的时候,那么就遍历完了所有起点为1的边。所以我们遍历的for循环就可以写成下面这种形式:
1 | for(int i=head[1];i!=0;i=edge[i].next) |
可以发现,我们遍历时访问的顺序和输入的顺序是刚好相反的
链式前向星代码如下:
1 |
|
最后要讲的东西可有可无,那就是,结构体中的u是可以省略的,为什么呢?我们可以把所有和结构体的u有关的代码其全部删去看看。其实以head[i]为源点,我们已经可以遍历所有以i为起点的边了,因此结构体中的u可以删去。
最终代码:
1 |
|