图的存储

约 340 个字 98 行代码 预计阅读时间 3 分钟

#图论

邻接矩阵

二维数组w[u][v]存储从u到v的边的权值
* 时间复杂度\(O(n^2)\)
* 空间复杂度\(O(n^2)\)
适合在点数不多的稠密图上使用

边集数组

边集数组e[i]存储第i条边的{起点u,终点v,边权w},常用结构体
* 时间复杂度\(O(mn)\)
* 空间复杂度\(O(m)\)

C++

struct edge{
int u,v,w;
};
vis[N];
void dfs(int u){
    vis[u]=true;
    for(int i=1;i<=m;i++){
        if(e[i].u==u){
            int v=e[i].v,w=e[i].w;
            printf("%d,%d,%d",u,v,w);
            if(vis[v]) continue;
            dfs(e[i].v);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    cin>>a>>b>>c;
    e[i]={a,b,c};
    }
    dfs(1);
}

邻接表

出边数组e[u][i]存储u点的所有出边{终点v和边权w}
* 时间复杂度\(O(n+m)\)
* 空间复杂度\(O(n+m)\)
各种图,不能处理反向边

C++

struct edge{int v,w;};
vector<edge> e[N];边集

void dfs(int u,int fa){
    for(auto ed:e[u]){
        int v=ed.v,w=ed.w;
        if(v==fa)continue;
        printf("%d%d%d",u,v,w);
        dfs(v,u);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
    }
    dfs(1,0);//从哪个点以及它的父节点,这里是对于树的深搜
    return 0;
}

链式邻接表

边集数组e[i]存储第j条边的{起点u,终点v,边权w}
表头数组h[u][i]存储u点的所有出边的编号
* 时间复杂度\(O(n+m)\)
* 空间复杂度\(O(n+m)\)
应用于各种图,能处理反向边

C++

struct edge{int u,v,w};
vector<edge> e;
vector<int> h[N];
void add(int a,int b,int c){
    e.push_back({a,b,c});
    h[a].push_back(e.size()-1);//起始下标是0
}
void dfs(int u,int fa){
    for(int i=0;i<h[u].size();i++){
    int j=h[u][i];
    int v=e[j].v,w=e[j].w;
    if(v==fa)continue;
    printf("%d%d%d",u,v,w);
    dfs(v,u);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);//也是树的深搜
    return 0;
}

常用在网络流中

链式前向星

一个表头数组悬挂多个链表
边集数组e[i]存储第i条出边的{终点v,边权w,下一条出边ne}
表头数组h[u]存储u点的第一条出边的编号
边的编号idx取0,1,2,3...
* 时间复杂度\(O(n+m)\)
* 空间复杂度\(O(n+m)\)

C++

struct edge{int v,w,ne;};
edge e[M];
int idx,h[N];
void add(int a,int b,int c){
    e[idx]={b,c,h[a]};//第一次h[a]肯定是-1,表示这是尾巴的边,后面的边都是插在前面的
    h[a]=idx;//意味着idx编号的这条边是a目前的第一条出边
    idx++;//接下来考虑下一条边
}
void dfs(int u,int fa){
    for(int i=h[u];~i;i=e[i].ne){
        int v=e[i].v,w=e[i].w;
        if(v==fa) continue;
        printf("%d%d%d",u,v,w);
        dfs(v,u);
    }
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    return 0;
}