图的存储

deepshits · 2025-11-23 10:42:40 · 个人记录

链式前向星

无边权

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
struct Edge{
    int to;
    int nxt;
};
Edge ed[MAXM];
int head[MAXN];
int len;
void add_edge(int u,int v){
    len++;
    ed[len].to=v;
    ed[len].nxt=head[u];
    head[u]=len;
} 
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++){
        cout<<i;
        for(int j=head[i];j!=0;j=ed[j].nxt){
            cout<<"-->"<<ed[j].to<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

有边权

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
struct Edge{
    int to;
    int val;
    int nxt;
};
Edge ed[MAXM];
int head[MAXN];
int len;
void add_edge(int u,int v){
    len++;
    ed[len].to=v;
    ed[len].val=w;
    ed[len].nxt=head[u];
    head[u]=len;
} 
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    for(int i=1;i<=n;i++){
        cout<<i;
        for(int j=head[i];j!=0;j=ed[j].nxt){
            cout<<"-->"<<ed[j].to<<'('<<ed[j].val<<')'<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

优点：对不会vector的人来说比较友好，时间比邻接矩阵优。

邻接矩阵

有边权

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
int g[MAXN][MAXN];
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v]=w;
        g[v][u]=w;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<g[i][j]<<' ';
        cout<<'\n';
    }
    return 0; 
} 

无边权

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
int g[MAXN][MAXN];
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u][v]=1;
        g[v][u]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<g[i][j]<<' ';
        cout<<'\n';
    }
    return 0; 
} 

优点：写的非常快

vector

有边权

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
vector<pair<int,int> > g[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
        g[v].push_back(make_pair(u,w));
    }
    for(int i=1;i<=n;i++){
        cout<<i<<':';
        for(auto j:g[i])
            cout<<j.first<<'('<<j.second<<')'<<' ';
        cout<<'\n';
    }
    return 0;
}

无边权

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
vector<int> g[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cout<<i<<':';
        for(auto j:g[i])
            cout<<j<<' ';
        cout<<'\n';
    }
    return 0;
}

优点：和链式前向星的时间和空间差不多，并且比链式前向星好写。