#|数据结构之图的存储结构（邻接表法） #|图

图的存储结构：邻接表法

产生条件：
邻接表法的定义：
邻接表法的特点：
邻接表法的代码定义：
邻接表法与邻接矩阵法的对比：

产生条件：当用邻接矩阵存储时：空间复杂度为O(|v|^2),太大
邻接表法的定义：

文章图片

例：

文章图片

文章图片

邻接表法的特点：

文章图片

ps：

1、存储空间 = 节点占用空间 + 边占用空间 2、邻接表的长度表示该顶点的出度 3、邻接表出现某一顶点的次数为该顶点的入度

邻接表法的代码定义：

#define MaxVertexTypeNum 100 typedef char VertexType; typedef int EdgeType; typedef struct ArcNode{//边表节点 int adjvex; //下一个节点的数据 struct ArcNode *next; // 指向下一个结点的指针 // InfoType info; //权值 }ArcNode; //边表节点的类型 typedef struct VNode{//顶点表节点 VertexType data; //顶点的数据 ArcNode *first; //指向边表的头指针 }VNode,AdjList[MaxVertexTypeNum]; // 邻接表类型 typedef struct{//邻接表 AdjList vetices; //所有结点的数据 int vexnum,arcnum; //节点数和边数 }ALGraph; //邻接表类型

邻接表法与邻接矩阵法的对比： 【#|数据结构之图的存储结构（邻接表法）】