6.3 图的存储结构

图的逻辑结构：多对多
图没有顺序存储结构，但可以借助二维数组来表示元素间的关系
数组表示法（邻接矩阵）
链式存储结构：①邻接表
②邻接多重表
③十字链表

邻接矩阵：
1、数组（邻接矩阵）表示法
建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间的关系）
设图A=(V,E)有n个顶点，则顶点表Vexs[n]
图的邻接矩阵是一个二维数组A.arcs[n][n]，定义为

①无向图的邻接矩阵表示法
无向图的邻接矩阵是对称的
顶点i的度=第i行（列）中1的个数
②有向图的邻接矩阵表示法
在有向图的邻接矩阵中，第i行表示以结点vi为尾的弧（即出度边）；第i列表示以结点vi为头的弧（即入度边）
有向图的邻接矩阵可能是不对称的
顶点的出度=第i行元素之和
顶点的入度=第i列元素之和
顶点的度=第i行元素之和+第i列元素之和
2、网（即有权图）的邻接矩阵表示法