B3600 [图论与代数结构 101] 图的代数表示题解

Daidly · 2021-07-10 10:48:58 · 题解

题目较简单，但代码较长。

邻接矩阵和权矩阵

两者差不多，只不过一个存是否有边 (0,1)，一个存边权。

使用一个二维数组 a 来表示。

若为无权图，a[u][v]=1 表示存在 u 到 v 的边，a[u][v]=0 表示不存在。

若为赋权图，a[u][v]=d 表示存储 u 到 v 的边的边权 d。

若为无向图，存两次即可。

复杂度

查询是否存在某条边：O(1)。

遍历一个点的所有出边：O(n)。

遍历整张图：O(n^2)。

空间复杂度：O(n^2)。

判断重边：

bool f1=0;
if(a[u][v]>0)f1=1;

在赋值 a[u][v] 前先查看 a[u][v] 之前是否被赋值过，若赋值过，则是有重边。

邻接矩阵和权矩阵代码：

void work1(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<a[i][j]<<" ";
        }cout<<endl;
    }
}

关联矩阵

使用一个二维数组 b 来表示。

关联矩阵即用一个矩阵来表示各个点和每条边之间的关系，所以当图不是赋权图且无自环时，可以用关联矩阵表示。

对于无向图：

第 i 条边 (u,v) 可表示为：

b[u][i]=1;
b[v][i]=1;

若 b[u][i]=1，表示边 i 上有点 u。

若 b[u][i]=0，表示边 i 和点 u 不相关联。

对于有向图：

第 i 条边 (u,v) 可表示为：

b[u][i]=1;
b[v][i]=-1;

若 b[u][i]=1，表示边 i 离开点 u。

若 b[u][i]=-1，表示边 i 进入点 u。

若 b[u][i]=0，表示边 i 和点 u 不相关联。

判断自环：

bool f2=0;
if(u==v)f2=1;

看 u 和 v 是否是同一个点，若是，则有自环。

关联矩阵代码：

void work2(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cout<<b[i][j]<<" ";
        }cout<<endl;
    }
}

邻接表

对于无权图：

使用一个动态数组 vector<int>c1[MAXN]; 来表示。

对于无向图:

c1[u].push_back(v);
c1[v].push_back(u);

对于有向图：

c1[u].push_back(v);

对于赋权图：

由于要存两个数，考虑使用 pair<int,int>，使用一个动态数组 vector<pair<int,int> >c2[MAXN]; 来表示。

其中 c2[i][j].first 表示第 i 个点的第 j 条边的对应点，c2[i][j].second 表示第 i 个点的第 j 条边的边权。

对于无向图:

c2[u].push_back(make_pair(v,d));
c2[v].push_back(make_pair(u,d));

对于有向图：

c2[u].push_back(make_pair(v,d));

邻接表代码：

void work3(){
    if(type2==0){
        for(int i=1;i<=n;++i){
            for(int j=0;j<c1[i].size();++j){
                cout<<c1[i][j]<<" ";
            }cout<<endl;
        }
    }else{
        for(int i=1;i<=n;++i){
            for(int j=0;j<c2[i].size();++j){
                cout<<c2[i][j].first<<" "<<c2[i][j].second<<" ";
            }cout<<endl;
        }
    }
}

正向表

用三个数组 A、B、Z 来表示。

对于 A 数组，A[1]=1，A[i]=A[i-1]+c[i-1].size()。

其中，c[i-1].size() 表示第 i-1 个点的连点个数。

注意 A 数组的点要到第 i+1 个。

对于 B、Z 数组，设长度为 num，初始为 0。

B 数组负责存对应点，Z 数组负责存对应边权，长度一样（按照点的顺序和存对应点的顺序），可结合代码理解。

正向表代码：

void work4(){
    num=0,A[1]=1;
    if(type2==0){
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c1[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c1[i].size();++j){
                B[++num]=c1[i][j];
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
    }else{
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c2[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c2[i].size();++j){
                B[++num]=c2[i][j].first;
                Z[num]=c2[i][j].second;
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<Z[i]<<" ";
        }cout<<endl;
    }
}

逆向表

对于无向图，逆向表与正向表相同，不用输出。

对于有向图：

顾名思义，“逆”就是把顺序逆过来。

对于无权图，使用一个动态数组 vector<int>c3[MAXN]; 来表示。

例如：边 (u,v)，可存为：c3[v].push_back(u);。

对于赋权图，使用一个动态数组 vector<pair<int,int> >c4[MAXN]; 来表示。

例如：边 (u,v)=d，可存为：c4[v].push_back(make_pair(u,d));。

其余与正向表类似，可结合代码理解。

逆向表代码：

void work5(){
    num=0,A[1]=1;
    if(type2==0){
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c3[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c3[i].size();++j){
                B[++num]=c3[i][j];
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
    }else{
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c4[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c4[i].size();++j){
                B[++num]=c4[i][j].first;
                Z[num]=c4[i][j].second;
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<Z[i]<<" ";
        }cout<<endl;
    }
}

写在最后

注意 1：正向表和逆向表的 B、Z 两个数组要开两倍 MAXN 大小，代码简用 MAXN<<1 来表示。
注意 2：当一个点邻接表中没有连边时，也要换行，如样例二，应该是：

总体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 305
int n,m,u,v,d;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
vector<int>c1[MAXN];
vector<pair<int,int> >c2[MAXN];
vector<int>c3[MAXN];
vector<pair<int,int> >c4[MAXN];
int A[MAXN],B[MAXN<<1],num,Z[MAXN<<1];
bool type1,type2,f1,f2;
void work1(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<a[i][j]<<" ";
        }cout<<endl;
    }
}
void work2(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cout<<b[i][j]<<" ";
        }cout<<endl;
    }
}
void work3(){
    if(type2==0){
        for(int i=1;i<=n;++i){
            for(int j=0;j<c1[i].size();++j){
                cout<<c1[i][j]<<" ";
            }cout<<endl;
        }
    }else{
        for(int i=1;i<=n;++i){
            for(int j=0;j<c2[i].size();++j){
                cout<<c2[i][j].first<<" "<<c2[i][j].second<<" ";
            }cout<<endl;
        }
    }
}
void work4(){
    num=0,A[1]=1;
    if(type2==0){
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c1[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c1[i].size();++j){
                B[++num]=c1[i][j];
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
    }else{
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c2[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c2[i].size();++j){
                B[++num]=c2[i][j].first;
                Z[num]=c2[i][j].second;
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<Z[i]<<" ";
        }cout<<endl;
    }
}
void work5(){
    num=0,A[1]=1;
    if(type2==0){
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c3[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c3[i].size();++j){
                B[++num]=c3[i][j];
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
    }else{
        for(int i=2;i<=n+1;++i){
            A[i]=A[i-1]+c4[i-1].size();
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<c4[i].size();++j){
                B[++num]=c4[i][j].first;
                Z[num]=c4[i][j].second;
            }
        }
        for(int i=1;i<=n+1;++i){
            cout<<A[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<B[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=num;++i){
            cout<<Z[i]<<" ";
        }cout<<endl;
    }
}
int main(){
    cin>>n>>m>>type1>>type2;
    if(type2==0){
        for(int i=1;i<=m;++i){
            cin>>u>>v;
            if(a[u][v]>0)f1=1;
            if(u==v)f2=1;
            if(type1==0){
                a[u][v]=1;
                a[v][u]=1;
                b[u][i]=1;
                b[v][i]=1;
                c1[u].push_back(v);
                c1[v].push_back(u);
            }else{
                a[u][v]=1;
                b[u][i]=1;
                b[v][i]=-1;
                c1[u].push_back(v);
                c3[v].push_back(u);
            }
        }
        if(f1==0)work1();
        if(f2==0)work2();
        work3();
        work4();
        if(type1==1)work5();
    }else{
        for(int i=1;i<=m;++i){
            cin>>u>>v>>d;
            if(a[u][v]>0)f1=1;
            if(type1==0){
                a[u][v]=d;
                a[v][u]=d;
                c2[u].push_back(make_pair(v,d));
                c2[v].push_back(make_pair(u,d));
            }else{
                a[u][v]=d;
                c2[u].push_back(make_pair(v,d));
                c4[v].push_back(make_pair(u,d));
            }
        }
        if(f1==0)work1();
        work3();
        work4();
        if(type1==1)work5();
    }
    return 0;
}

如果您看懂了或是对您有帮助，请点一个小小的赞吧，谢谢！

B3600 [图论与代数结构 101] 图的代数表示 题解

邻接矩阵和权矩阵

复杂度

判断重边：

邻接矩阵和权矩阵代码：

关联矩阵

对于无向图：

对于有向图：

判断自环：

关联矩阵代码：

邻接表

对于无权图：

对于赋权图：

邻接表代码：

正向表

正向表代码：

逆向表

对于有向图：

逆向表代码：

写在最后

总体代码如下：

B3600 [图论与代数结构 101] 图的代数表示题解