数据结构笔记——图的存储之十字链表、邻接多重表

╰+攻爆jí腚メ 2023-02-17 11:21 14阅读 0赞

## **一、邻接矩阵、邻接表存储有向图** ##

![20200613191223319.png][]**有向图**

![20200613192446927.png][]**邻接矩阵**![202006131913213.png][]**邻接表**

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

![20200613191442125.png][]

## **二、十字链表存储有向图** ##

![20200613191643974.png][]**弧结点**

![20200613191706518.png][]**顶点结点**![20200613191827771.png][]**有向图**![20200613191841465.png][]**十字链表**

## **三、十字链表性能分析** ##

空间复杂度O（|V| + |E|）

Q1：如何找到指定顶点的所有出边？——顺着**绿色**线路找

Q2：如何找到指定顶点的所有入边？——顺着**橙色**线路找

## **四、邻接矩阵、邻接表存储无向图** ##

![20200613192523248.png][]**无向图**![20200613192540923.png][]**邻接矩阵**![20200613192609962.png][]**邻接表**

## **五、邻接多重表存储无向图** ##

![20200613192724621.png][]**边结点**![20200613192745967.png][]**顶点结点**![20200613192810441.png][]**无向图**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]**邻接多重表**

**两种情况**

**①当去掉一条边时**

![20200613193301196.png][]**无向图**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]**邻接多重表**

**②去掉一个顶点和一条边时**

![20200613193418315.png][]**无向图**![20200613193438526.png][]**邻接多重表**

空间复杂度：O（|V| + |E|）

删除边、删除节点等操作很方便

**注意：邻接多重表只适用于存储无向图**

六、总结

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

[20200613191223319.png]: https://img-blog.csdnimg.cn/20200613191223319.png
[20200613192446927.png]: https://img-blog.csdnimg.cn/20200613192446927.png
[202006131913213.png]: https://img-blog.csdnimg.cn/202006131913213.png
[20200613191442125.png]: https://img-blog.csdnimg.cn/20200613191442125.png
[20200613191643974.png]: https://img-blog.csdnimg.cn/20200613191643974.png
[20200613191706518.png]: https://img-blog.csdnimg.cn/20200613191706518.png
[20200613191827771.png]: https://img-blog.csdnimg.cn/20200613191827771.png
[20200613191841465.png]: https://img-blog.csdnimg.cn/20200613191841465.png
[20200613192523248.png]: https://img-blog.csdnimg.cn/20200613192523248.png
[20200613192540923.png]: https://img-blog.csdnimg.cn/20200613192540923.png
[20200613192609962.png]: https://img-blog.csdnimg.cn/20200613192609962.png
[20200613192724621.png]: https://img-blog.csdnimg.cn/20200613192724621.png
[20200613192745967.png]: https://img-blog.csdnimg.cn/20200613192745967.png
[20200613192810441.png]: https://img-blog.csdnimg.cn/20200613192810441.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200613192828515.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200613193301196.png]: https://img-blog.csdnimg.cn/20200613193301196.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200613193315257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200613193418315.png]: https://img-blog.csdnimg.cn/20200613193418315.png
[20200613193438526.png]: https://img-blog.csdnimg.cn/20200613193438526.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200613193610475.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70