邻接表是什么

邻接表是一种存储图的链式存储结构，和邻接矩阵功能一样。

假设一个双向图

我们如果用邻接矩阵储存就会是这样(没有连接的我们认为权值是inf)
0 6 inf inf 4
6 0 8 inf inf
inf 8 0 2 3
inf inf 2 0 inf
4 inf 3 inf 0
我们这时候会发现，邻接矩阵会浪费一些空间，也就是没有连接的边，他也会存入一个最大值

假如用邻接表储存呢？
首先邻接表由两个主要的部分组成

1. 头节点：用来储存节点编号
2. 表节点：用来储存权值和所连接的节点标号

这时我们会发现邻接矩阵的空间复杂度是O(n^2)
邻接表的空间复杂度是O(n+m)
所以在稀疏图中邻接表比较省空间

邻接表在算法中的应用

优化最短路算法（SPFA,迪杰斯特拉）
其中有邻接表在实战时如何创建和如何遍历
可以用这个题来练手
参考代码：

//迪杰斯特拉,优先队列优化
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;

typedef pair<int,int> PII;
const int N=10001;
const int inf=0x3f3f3f3f;
struct no
{
    int a;
    int b;
    int c;
    int next;
}mp[N];
int n,m,tot;
int book[N];
int dis[N];
int head[N]; 
void add(int a, int b, int c)//创建邻接表
{
    mp[tot].b=b;
    mp[tot].c=c;
    mp[tot].next=head[a];
    head[a]=tot++;
}
void dij()
{
    memset(book,0,sizeof book);
    memset(dis,inf,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII> > qu;
    dis[1]=0;
    qu.push({0,1});
    while(qu.size())
    {
        PII ne=qu.top();
        qu.pop();
        int u=ne.second;
        if(book[u]) continue;
        book[u]=1;
        for(int j=head[u]; j!=-1; j=mp[j].next)//遍历邻接表
        {
            int go=mp[j].b;
            if(!book[go]&&dis[go]>dis[u]+mp[j].c)
            {
                dis[go]=dis[u]+mp[j].c;
                qu.push({dis[go],go});
            }    
        } 
    }
    cout<<dis[n]<<endl;
}
int main()
{
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        tot=0;
        memset(head,-1, sizeof head);
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        dij();
    }
    return 0;
}

//SPFA
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int N=1e4+5;
const int inf=0x3f3f3f3f;
int n,m,t;
int dis[N];
int pre[N];
int book[N];
struct no
{
    int a;
    int b;
    int v;
    int next;
}mp[N];
void add(int a,int b,int v)
{
    mp[t].a=a;
    mp[t].b=b;
    mp[t].v=v;
    mp[t].next=pre[a];
    pre[a]=t++;
}
void spfa(int n)
{
    queue<int>q;
    memset(dis,inf,sizeof dis);
    memset(book,0,sizeof book);
    book[1]=1;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        book[u]=0;
        for(int i=pre[u]; i!=-1; i=mp[i].next)
        {
            int v=mp[i].b;
            if(dis[v]>dis[u]+mp[i].v)
            {
                dis[v]=dis[u]+mp[i].v;
                if(!book[v])
                {
                    book[v]=1;
                    q.push(v);
                }
            }
        }
    }
    printf("%d\n",dis[n]);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        t=1; 
        memset(pre,-1,sizeof pre);
        for(int i=1; i<=m ;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a!=b)
            {
                add(a,b,c);
                add(b,a,c);
            }
        } 
        spfa(n);
    }
    return 0;
}