邻接链表的使用

我们知道，如果一个图比较小的话，可以使用邻接矩阵来存图，但当图比较大的话，再使用邻接矩阵，那么空间就会爆炸,所以我们采用邻接链表来优化空间。

构建方法

顾名思义，邻接链表也是一种链表，包括表头，指向的边和下一个链表的位置,若为带权图，还能保存权值。

int head[maxn];//表头索引
struct edge{
	int to,next,w;//to表示指向的点，next表示链表的下一个位置，w表示边权
}e[maxn<<1];//无向图为两倍空间

添加元素的方法也十分简单,就跟链表的构建方法一样。

int cnt;//新建链表的位置
void add(int u,int v,int w)
{
	e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}

遍历 $u$u节点的所有边方法如下:

	for(int i=head[u];i;i=e[i].next)
    {
    	//e[i].to即为与u相连的一个节点
	}

包装

对于有多个图的题目，你甚至可以把邻接链表包装起来以达到优化代码长度的效果

template<int maxn>
struct LJLB{
	int head[maxn],cnt;
    struct edge{
    	int to,next,w;
    }e[maxn];
    LJLB()
	{
    	memset(head,0,sizeof head);
        memset(e,0,sizeof e);
        cnt=0;
    }
    void add(int u,int v,int w)
	{
    	e[++cnt].to=v;
 		e[cnt].next=head[u];
  		e[cnt].w=w;
    	head[u]=cnt;
	}
    edge & operator[](const int i){ return e[i]; }
};

使用方法和之前一样。