数据结构与算法-图论邻接表【十五】

向右看齐 2023-03-04 06:31 34阅读 0赞

#### 链式存储 （链式表示） ####

上一话说的是邻接矩阵方式去存储图，这一话用链表去存储图  
链式表表示法----【邻接表/ 邻接多重表 / 十字链表】

#### 邻接表 ####

将所有的顶点数据仍然存放在一维数组内。  
    这个一维数组比较特殊，顶点数组的每个元素都指向一个邻接点单链表。

咱们以上一个邻接矩阵用到的一个有向图和无向图为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70]

##### 无向图 的邻接表 #####

第一个`无向图`的邻接表可以这样表示：

实际上邻接表是不唯一的，每一个顶点元素指向一个单链表，单链表的所有节点都是顶点元素的邻接点，顺序是可以随意更改的，比如上面的表中，A指向的单链表，B和C的顺序可以改变的。

如果`无向图`有`n`个顶点，`e`条边，那么用邻接表来存储这个图需要 `n`个头结点 和 `2e`个表结点。 更适合存储稀疏图。  
     `无向图` 中顶点`Vi`的度为该顶点指向的单链表中的节点的个数。

问题:上面第一个无向图，5条边在邻接表里面存了两次，一共10个节点。

##### 有向图 的邻接表 #####

咱么以上面`第二个有向图`为例，邻接表的表示为

特点： 该邻接表求顶点的出度容易，求入度困难。

1.  顶点Vi的出度，就是这个顶点指向的单链表中节点的个数。
2.  顶点Vi的入度， 必须要遍历非Vi顶点所指向的所有单链表。

##### 有向图 的逆邻接表 #####

咱们可以改变一下存储方式，上面的邻接表，每一个顶点元素指向的单链表存储的是该顶点的`出度边`指向的元素。 比如以第二个有向图的顶点 A 为例，他指向单链表中的元素为顶点B，为A指向B的弧尾。

咱们可以存储以A为入度边的弧尾的元素，这种类型的邻接表叫`逆邻接表`。

还是以上面图中的第二个有向图为例：

特点： 该邻接表求顶点的 入度容易，求出度困难。

1.  顶点Vi的入度，就是这个顶点指向的单链表中节点的个数。
2.  顶点Vi的出度， 必须要遍历非Vi顶点所指向的所有单链表。

--------------------

#### 邻接表的特点 ####

1.  很快速方便的找到某个顶点的“邻接点”
2.  节约稀疏图（点多边少）的空间
3.  （针对无向图）求顶点的度很方便，求该顶点指向的单链表的节点个数即可
4.  （针对有向图）求顶点的出度方便，该顶点指向单链表的节点个数。【对于入度不方便，需要遍历所有单链表】
5.  （针对有向图）如果是逆邻接表，求顶点的入度方便，入度就为该顶点指向的单链表的节点个数。【对于出度不方便，需要遍历所有单链表】

对于有向图来说，邻接表和逆邻接表只能求出度或者入度容易，不能同时求出，可以将邻接表和逆邻接表结合起来改良为十字链表（存储的边节点个数不变，只是边节点存储的内容会多一些）。

对于无向图来说，求出度和入度容易，添加和删除麻烦，并且无向图邻接表的 边节点是存储了两份，所以改良为邻接多重表（将存储的边节点存储为一份，不会重复，边节点的内容也同样会多出来）

--------------------

#### 邻接矩阵与邻接表的区别 ####

1.  对于任意一个无向图，邻接矩阵是唯一的。但是邻接表不唯一，因为顶点指向的单链表各个节点的顺序是任意的，可以用头插法，也可以用尾插法。
2.  邻接矩阵的空间复杂度为`O(n^2)`, 邻接表的空间复杂度`O(n+e)` n为顶点个数，e为边的条数（也可以理解为所有指向的单链表中节点的个数）。
3.  邻接矩阵多适用于稠密图（点多边多），邻接表多适用于稀疏图（点多边少 ）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70]: /images/20230208/7e183a5660284910a4060dc883d8ba3f.png