讲课链接

图的存储

约 100 个字 81 行代码 预计阅读时间 1 分钟

直接存

struct EDGE
{
    int u,v;
}e[1000];
int total;//边的数量
void init()
{
    total=0;
}
void addEdge(int u,int v)
{
    e[++total]={u,v};
}
void printAllEdge()
{
    cout<<e[i].u<<" "<<e[j].v<<"\n";
}

邻接矩阵

int e[100][100];
void init(int n)
{
    for(int i=0;i<n;++i)
        memset(e[i],0,sizeof(int)*(n));
}
void addEdge(int u,int v)
{
    e[u][v]=1;
}
void printAllEdge()
{
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(e[i][j])
                cout<<i<<" "<<j<<"\n";
        }
    }
}

邻接表

vector<int> e[1000];//表示点i连接的边的集合
void init(int n)
{
    for(int i=0;i<n;++i)
        e[i].clear();
}
void addEdge(int u,int v)
{
    e[u].push_back(v);
}
void printAllEdge()
{
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<e[i].size();++j)
            cout<<i<<" "<<e[i][j]<<"\n";
    }
}

链式前向星

和邻接表类似

struct EDGE
{
    int v;//表示点i连的这条边的对应的点
    int next;//表示点i连的下一条边的下标
}e[1000];
int head[100];//表示点i最近连的一条边的下标
int total;//边的数量
void init(int n)
{
    memset(head,-1,sizeof(int)*(n));
    total=0;
}
void addEdge(int u,int v)
{
    e[++total]={v,head[u]};
    head[u]=total;
}
void printAllEdge()
{
    for(int i=0;i<n;++i)
    {
        for(int j=head[i];j!=-1;j=e[j].next)
            cout<<i<<" "<<e[j].v<<"\n";
    }
}

邻接矩阵适用于稠密图

邻接表和链式前向星适用于稀疏图

在 $|E|<5e5$ 时，邻接表更快，反之链式前向星

在边权只有0和一种正边权的图上，可以用deque代替priority_queue，这样dijkstra变成01BFS加速