考研数据结构第6章图|图的存储结构1.邻接矩阵法2.邻接表法-一一网

这是我参与8月更文挑战的第21天，活动详情查看：8月更文挑战

图的存储结构

1.邻接矩阵法

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵

对非带权图，结点数为n的图G的邻接矩阵A是n×n。

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵

对带权图，结点数为n的图G的邻接矩阵A是n×n。

图的邻接矩阵存储结构定义代码

#define  MaxVertexNum  100        //顶点数目的最大值
typedef  char  VertexType;            // 顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型 
typedef  struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType  Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表 
int  vexnum,arcnum;                               //图的当前顶点数和弧数
}MGraph;
复制代码

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵

注意

无向图的邻接矩阵是对称矩阵，对规模较大的邻接矩阵可使用压缩存储
邻接矩阵表示法的空间复杂度是O(?2),其中n为图的顶点数?
对无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数,正好是第i个顶点的度TD(??)
对有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数,正好是第i个顶点的出度OD(??)（或入度ID(??)）
邻接矩阵法存储图，确定图中任意两个顶点之间是否有边相连只需O(1)时间复杂度
但要确定图中有多少条边，则必须遍历整个二维数组，时间复杂度为O(?2)
稠密图适合使用邻接矩阵的存储表示

2.邻接表法

对图G中的每个顶点??建立一个单链表，第i个单链表中的结点表示依附于顶点??的边（对有向图是以顶点??为尾的弧），这个单链表称为顶点??的边表（对有向图称为出边表）

邻接表中有两种结点：顶点表结点和边表结点

无向图邻接表法

有向图邻接表法

图的邻接表法存储结构定义代码

#define  MaxVertexNum  100     //图中顶点数目的最大值
typedef  struct  ArcNode{            //边表结点
int  adjvex;                              //该弧指向的顶点位置
struct  ArcNode  *next;        //指向下一条弧的指针 
//InfoType  info;                    //网的权值
}ArcNode;
typedef   struct  VNode{             //顶点表结点
VertexType  data;                 //顶点信息
ArcNode  *first;                    //指向第一条依附于该顶点的弧的指针
}VNode,AdjList[MaxVertexNum]; 
typedef  struct{
AdjList  vertices; //邻接表
int  vexnum,arcnum;        //图的顶点数与弧数
}ALGraph;
复制代码