图的储存方式——边的储存-白红宇

图的储存方式——边的储存

阅读量：6412 次

发布时间：2019-06-23

本文共 3176 字，大约阅读时间需要 10 分钟。

说起图的储存就先要说到变的储存了！

说起边有些童鞋恐怕还分不清楚什么和什么吧！

好，下面我们就来说一下边吧！

一。边的分类

边可以通过有无方向分为

1.有向边

2.无向边

大都数情况下我们可以把无向边看作是两条有向边

边通过有无权值分为

1.带权边

2.无权边

大多数情况下我们把无权边看作是边权为1的带权边

说完边的分类，那我们下面就要说到边的储存了！

二。边的储存

边有以下几种储存方式：

1.邻接矩阵（本人认为这是最好写的的一种了！）

优点：实现简便，运用位运算和矩阵算法优化的时候更方便

缺点：时空复杂度较大

2.链表储存

　　优点：时空复杂度较小

　　缺点：实现相对复杂

3.边集数组

　　优点：容易对边进行处理，对边进行排序，方便整体处理

　　缺点：难以对图进行遍历，难以求出每个节点相邻的边的相邻节点

邻接矩阵

对于一个给定的图，有n个点m条边，那我们若要储存这个图那就要弄一个n*m的邻接矩阵

注意：

① 在简单应用中，可直接用作为图的邻接矩阵(顶点表及顶点数等均可省略)。

② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的。

③无向图的邻接矩阵是，对规模特大的邻接矩阵可压缩存储。

④邻接矩阵表示法的S(n)=0(n 2 )。

⑤建立无向网络的算法。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 10000using namespace std;int e[N][N],vis[N];int n,m,a,b,c;void bfs(int x){    vis[x]=1;    for(int i=1;i<=n;i++)    {        if(e[x][i]&&!vis[i])         bfs(i);    }}int main(){    scanf("%d%d",&n,&m);//n个点，m条边     for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&a,&b,&c);        e[a][b]=c;//有向边     }    bfs(1);    return 0;}

时空复杂度均为o(n^2)!

邻接表

对于图来说，邻接矩阵村边是一个很不错的选择！但是对于点数十分稀疏的图来说，这种方法是十分浪费空间的！！

so，我们就有了另外一种储存边的方法——邻接表！

那么你肯定会问邻接表是什么鬼，那是怎么用的？？

邻接表的处理方法

1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 10000#define oo 123456using namespace std; int head[N],n,m,a,b,c,num;bool vis[N];struct Edge{    int next;//下一条边的编号     int to;//这条边到达的点     int dis;//这条边的长度 }edge[N];void ins(int from,int to,int dis){        edge[++num].next=head[from];        edge[num].to=to;        edge[num].dis=dis;        head[from]=num; }int dfs(int x){    vis[head[x]]=1;    for(int i=1;i<=n;i++)    {        if(!vis[head[i]])          dfs(i);    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%d%d%d",&a,&b,&c);        ins(a,b,c);    }    dfs(1);    return 0;}

vector

啊啊啊！这是些什么鬼！有没有感觉前面这些东西太恶心了！完全记不住啊！

好，那我们下面来弄个简单的！

stl中的vector！

vector可以看做一个不用人为开大小的一个数组，我们可以对每一个节点都使用一个vector，然后把每个节点的信息都储存在这个点的vector中即可。

对于一个有边权的图来说，有pair讲点的编号和权值结合起来储存在vector中

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 100000#define maxn 123456using namespace std;int m,n,x,y,z;bool vis[N];vector
           
            
              >vec[N];void bfs(int x){ vis[x]=1; for(int i=0;i

边集数组

边集数组就是将输入的边用一个数组保存下来，而不是将其与点放在一起。

这种方法一般是在不需要点的信息时使用，不要遍历整张图，只需要每个边的信息时使用，如并查集。

当然也存在一种算法可以在使用边集数组时，十分迅速的将点的信息求出。

这种方法就是向前星。

我们可以再输入边的时候将边按照出点的顺序进行排序，这样每一个点的所有出边都是连续的。

扫一遍整张图后，我们就可以知道每一个点的所有出边所在的区间。

对于无向边我们就要存两遍！

由于要对给出的每一条边进行排序，所以时空复杂度较大。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 100000#define maxn 123456using namespace std;int n,m,a,b,c,len,l[N],r[N];bool vis[N];struct Edge{    int x,y,z;}edge[N];int cmp(Edge a,Edge b){    return a.x