数据结构之图（存储）

目录

邻接矩阵法

正常图

这里无向图一条边代表两个一（A行B列为1则B行A列一定为1，同理0也是）
这里有向图的一条边代表一个1（A行B列为1就代表有A指向B的边）

如何求顶点的度（入度/出度）
无向图
比如求B检查B那一行（或那一列）对应有几个1
它的度就是多少
有向图
比如求A的入度和出度
出度，检测A那一行有几个1
入度，检测A那一列有几个1

带权图的存储

当两条边没有互相连接的话
对应的矩阵上面可以填无穷
有一种是在自己对自己的时候写的是0（知道就行）

性能分析

邻接矩阵适合用于存储稠密图
当边比较少时会浪费很多空间

无向图的邻接矩阵可以只存上三角/下三角区域
这是对称矩阵的压缩存储

邻接矩阵法的性质

1.A^n矩阵内的元素代表的东西
适用于无向图和有向图

A^2
根据矩阵的性质奥（线性代数学过）
A^n【i】【j】的值代表从i节点到j及诶单有几条长度为n的路径
比如图中这个吧
A^2=A11×A14((A->B)×(B->D))+…如果=0就说明A从B带D路径不通
如果为1的话说明A到B和B到D都通，那长度为2的路不就有一条咯
后面的同理

A^2和A相乘不就是A ^3
然后[A][D]=1(这个1是A到A有一条路径长为2的路径)×0（没有一套从A到D路径为1的路径）+0×1+1（有一条从A到C的路径长为2）×1（有一条从C到D长度为1道路一条）+0×0=1（代表从A到D长度为3的路有一条）

小总结

邻接表法

顺序+链式储存

类似于树中的孩子表示法

有向图

无向图的度和有向图的出度是比较好找的（遍历对应节点的链表即可）
有向入度的话就把所有的节点的边链表遍历一遍
邻接表的表示方式不为1

但是邻接矩阵是唯一的奥

十字链表（储存有向图）

两种结构体奥
从绿色指针域一种遍历是该节点指向的节点
从橙色节点的话遍历是指向自身的节点

邻接多重表（储存无向图）

上面两种方法的弊端

邻接多重表

就是
比如找A吧
从firstedge往后走
第一条边不是0-1（A-B这条边）
你从橙色指针域走的话
还是找与A相连的边，如果你找绿色指针域的话
就是和A相连的另一个顶点（这里是B奥）的另一条边

删除（节点或边的删除）也很方便

总结