图存储之邻接表法

痛定思痛。 2022-12-15 14:02 168阅读 0赞

## 一 概述 ##

当一个图为稀疏图时，使用邻接矩阵法显然要让费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

## 二 邻接表 ##

邻接表，是指对图G中的每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi位尾的弧），这个单链表就称为顶点vi的边表（对于有向图则称为出边表）。边表的头指针和顶点数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点：顶点表结点和边表结点。

![20201017101949360.png][]

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成。

<table> 
 <tbody> 
  <tr> 
   <td>无向图邻接表表示法实例</td> 
   <td><img alt="" height="116" src="https://img-blog.csdnimg.cn/20201017102501424.png" width="413"></td> 
   <td>有向图邻接表表示法实例</td> 
   <td><img alt="" height="177" src="https://img-blog.csdnimg.cn/2020101710252477.png" width="396"></td> 
  </tr> 
 </tbody> 
</table>

## 三 图的邻接表存储结构定义 ##

#define MaxVertexNum 100        //图中顶点数目的最大值
    typedef char VertexType;        //图中顶点数据类型
    typedef struct ArcNode{         //边表结点
        int adjvex;                 //该弧所指向的顶点的位置
        struct ArcNode *next;       //指向下一条弧度的指针 
        int info;                   //网的边权值
    }ArcNode;
    
    typedef struct VNode{           //顶点表结点
        VertexType data;            //顶点信息
        ArcNode *first;             //指向第一条依附该顶点的弧的指针
    }VNode,AdjList[MaxVertexNum];
    
    typedef struct {
        AdjList vertices;           //邻接表
        int vexnum,arcnum;          //图的顶点数和弧数
    }ALgraph;                       //ALgraph是以邻接表存储的图类型

## 四 图的邻接表存储方法的特点 ##

1.  若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
2.  对于稀疏图，采用邻接表示将极大地节省存储空间。
3.  在邻接表中，给定一个顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立即查到，而在邻接表中则需要在相应结点对应的表中查找另一个结点，效率较低。
4.  在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表的结点个数；但是求其顶点的入度则需要遍历整个邻接表。因此，可以采用逆邻接表的存储方式来求解给定顶点的入度。
5.  图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的连接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

[20201017101949360.png]: /images/20221123/86761158348947a09780aad0e5e70904.png