图的存储结构
2020-03-18 23:30:59 4 举报数据结构图的存储方案
作者其他创作
大纲/内容
adjvex下标
v3
∞ ∞ ∞ 0
v0
0 ∞ ∞ 5
next
v1出度
十字链表
计算入度：每个顶点出发，沿着蓝色的边前进，直到某个变得headlink为\\，经过边的数量即为出度计算出度：从每个顶点出发，沿着红色的边前进，直到某个边的taillink为\\，经过边的数量即为
1
2
0
v1
v2
3
\\
邻接表
有向图
边数组（邻接矩阵）：
data
1 1 0 0
1 0 1 0
v0v1v2v3
下标
0 1 1 1
对于网：只需要有向图的基础上增加一个weight的权值域
v1入度
网
此时很容易得到某个顶点的出度若要得到某个顶点的入度，只需要建立一个逆邻接表即：对每一个顶点都建立一个以该顶点为弧头的表
Wij：权值存在0： i=j∞：权值不存在
tailvex：弧起点所在顶点的下标headvex：弧终点所在顶点的下标headlink：是指入边指针域，指向终点相同的下一条边taillink：是指出边指针域，指向起点相同的下一条边
v0 v1 v2 v3
firstedge
顶点数组：
为了解决邻接表对于出度入度方面统计的需要逆邻接矩阵的缺点十字链表就是吧邻接矩阵和逆邻接矩阵结合起来
v4
1 0 9 ∞
图的邻接矩阵就是用两个数组来表示图其中一个数组存储图中的顶点信息另一个二维数组（称为邻接矩阵）存储图中的边或弧的信息
v1的度为2
6 ∞ 0 ∞
将节点存入数组并将关联的节点存入链表
无向图
9
0 0 0 1
为此我们需要重新设计顶点表结构和边表节点结构
index
firstin
firstout
边表节点
1 1 0 1
顶点表
/
主对角线
index：在数组中的下标data：数据域firstin：第一条以该结点为弧尾的边firstout：第一条以该结点为弧头的边
6
5
邻接矩阵
tailvex
headvex
headlink
taillink
0 0 0 0
0 条评论
下一页
