邻接表

teach

简单讲解邻接表

邻接表

看完链式前向星之后，我们来看一下它的小伙伴————邻接表。邻接表相对于普通矩阵记录边和查找边速度会更加快，唯一的不同就是构造起来代码量会更多，下面直接先上代码

1
2
3
4
5
6
7
8
9
10
11
12
for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&ui,&vi,&ti);
            a[ui][0]++;/*ui是起点，这里记录以ui为起点的边的数量*/
            a[vi][0]++;/*同上*/
            a[ui][a[ui][0]]=i;/*这个是边的编号*/
            a[vi][a[vi][0]]=i+m;/*同上*/
            l[i+m][1]=ui;/*记录编号为i+m的边的终点*/
            l[i+m][2]=ti;/*记录编号为i+m的边的权值*/
            l[i][1]=vi;/*同上上*/
            l[i][2]=ti;/*同上上*/
        }

简介

通过上面的代码我们可以发现，它跟链式前向星真的很像，因为同样是运用了链表的思想，这样做的缺点就是不能用O(1)的时间找到两点之间有没有边，可是这样做dfs和bfs却会比普通矩阵速度要快上不少，为什么呢？

因为通常情况下，两个点之间未必会有边的，而对同一个点进行查询，邻接表只需要查O(x)次，x代表当前点所拥有的边，而普通矩阵要查O(n-1)次，n代表点的数量，所以结果出来就显而易见了，对一张图，普通矩阵要查O(n²),而邻接表最多不超过O(n*m)，如果还是不理解，可以看回链式前向星的图表，相信你会理解得更好的~