存储结构方式之邻接表详解
对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（adjacency list），即数组与链表相结合的存储方法。
邻接表的处理方法是这样的。
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。
例如图7-4-6就是一个无向图的邻接表结构。
若是有向图，邻接表的结构是类似的，如图7-4-7，以顶点作为弧尾来存储边表容易得到每个顶点的出度，而以顶点为弧头的表容易得到顶点的入度，即逆邻接表。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如图7-4-8所示。
下面示例无向图的邻接表创建：（改编自《大话数据结构》）
c++ code #includeusing namespace std;#define maxvex 100 /* 最大顶点数,应由用户定义 */typedef char vertextype; /* 顶点类型应由用户定义 */typedef int edgetype; /* 边上的权值类型应由用户定义 */typedef struct edgenode /* 边表结点 */{ int adjvex; /* 邻接点域,存储该顶点对应的下标 */ edgetype weight; /* 用于存储权值,对于非网图可以不需要 */ struct edgenode *next; /* 链域,指向下一个邻接点 */} edgenode;typedef struct vextexnode /* 顶点表结点 */{ vertextype data; /* 顶点域,存储顶点信息 */ edgenode *firstedge; /* 边表头指针 */} vextexnode, adjlist[maxvex];typedef struct{ adjlist adjlist; int numnodes, numedges; /* 图中当前顶点数和边数 */} graphadjlist;void createalgraph(graphadjlist *gp){ int i, j, k; edgenode *pe; cout << 输入顶点数和边数(空格分隔）: gp->numnodes >> gp->numedges; for (i = 0 ; i numnodes; i++) { cout << 输入顶点信息： gp->adjlist[i].data; gp->adjlist[i].firstedge = null; /* 将边表置为空表 */ } for (k = 0; k numedges; k++) /* 建立边表 */ { cout << 输入边(vi,vj)的顶点序号i,j（空格分隔）: i >> j; pe = (edgenode *)malloc( sizeof(edgenode)); pe->adjvex = j; /* 邻接序号为j */ /* 将pe的指针指向当前顶点上指向的结点 */ pe->next = gp->adjlist[i].firstedge; gp->adjlist[i].firstedge = pe; /* 将当前顶点的指针指向pe */ pe = (edgenode *)malloc( sizeof(edgenode)); pe->adjvex = i; pe->next = gp->adjlist[j].firstedge; gp->adjlist[j].firstedge = pe; }}int main( void){ graphadjlist gl; createalgraph(&gl); return 0;} 这里的邻接点插入使用了单链表创建中的头插法，对于无向图来说，一条边对应都是两个顶点，所以在循环中，一次就针对i和j分别进行了插入。
脉冲型翻斗式雨量计是什么，它的工作原理是怎样的
云计算的未来将会是无服务器吗
InstantEye Robotics宣布推出多功能小型无人机系统
GTX 16系列全线停产！
小米max2什么时候上市?oppor11首发骁龙660,小米max2同配置今日发布只要1499!oppor11能否再续辉煌?
存储结构方式之邻接表详解
MCU内部DataFlash的特点原理揭秘
电感和磁珠的区别
TDA2030A音频功放及应用
使用最新的机器学习技术进行恶性肿瘤治疗，可以缓解患者在治疗中的痛苦
苏州洲际酒店，使用智能机器人「润」做服务员，会迎宾、送茶等服务
工业测量中的噪声干扰问题
浙江萧山首个内河智能岸电系统在江顺建材码头正式投入使用
基于软件无线电中频接收系统的设计方案
谷歌量子计算机新突破 可几秒内完成47年的任务
先楫半导体发布多个系列高性能微控制器产品
数字化施工引领基础设施建设新潮流
我国IPv6规模部署加速,2025年完成向下一代互联网的平滑演进升级
如何运用数字I/O来保护继电器
关于加速度传感器7102A-0100的几种应用
邻接表的处理方法是这样的。
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。
例如图7-4-6就是一个无向图的邻接表结构。
若是有向图，邻接表的结构是类似的，如图7-4-7，以顶点作为弧尾来存储边表容易得到每个顶点的出度，而以顶点为弧头的表容易得到顶点的入度，即逆邻接表。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如图7-4-8所示。
下面示例无向图的邻接表创建：（改编自《大话数据结构》）
c++ code #includeusing namespace std;#define maxvex 100 /* 最大顶点数,应由用户定义 */typedef char vertextype; /* 顶点类型应由用户定义 */typedef int edgetype; /* 边上的权值类型应由用户定义 */typedef struct edgenode /* 边表结点 */{ int adjvex; /* 邻接点域,存储该顶点对应的下标 */ edgetype weight; /* 用于存储权值,对于非网图可以不需要 */ struct edgenode *next; /* 链域,指向下一个邻接点 */} edgenode;typedef struct vextexnode /* 顶点表结点 */{ vertextype data; /* 顶点域,存储顶点信息 */ edgenode *firstedge; /* 边表头指针 */} vextexnode, adjlist[maxvex];typedef struct{ adjlist adjlist; int numnodes, numedges; /* 图中当前顶点数和边数 */} graphadjlist;void createalgraph(graphadjlist *gp){ int i, j, k; edgenode *pe; cout << 输入顶点数和边数(空格分隔）: gp->numnodes >> gp->numedges; for (i = 0 ; i numnodes; i++) { cout << 输入顶点信息： gp->adjlist[i].data; gp->adjlist[i].firstedge = null; /* 将边表置为空表 */ } for (k = 0; k numedges; k++) /* 建立边表 */ { cout << 输入边(vi,vj)的顶点序号i,j（空格分隔）: i >> j; pe = (edgenode *)malloc( sizeof(edgenode)); pe->adjvex = j; /* 邻接序号为j */ /* 将pe的指针指向当前顶点上指向的结点 */ pe->next = gp->adjlist[i].firstedge; gp->adjlist[i].firstedge = pe; /* 将当前顶点的指针指向pe */ pe = (edgenode *)malloc( sizeof(edgenode)); pe->adjvex = i; pe->next = gp->adjlist[j].firstedge; gp->adjlist[j].firstedge = pe; }}int main( void){ graphadjlist gl; createalgraph(&gl); return 0;} 这里的邻接点插入使用了单链表创建中的头插法，对于无向图来说，一条边对应都是两个顶点，所以在循环中，一次就针对i和j分别进行了插入。
脉冲型翻斗式雨量计是什么，它的工作原理是怎样的
云计算的未来将会是无服务器吗
InstantEye Robotics宣布推出多功能小型无人机系统
GTX 16系列全线停产！
小米max2什么时候上市?oppor11首发骁龙660,小米max2同配置今日发布只要1499!oppor11能否再续辉煌?
存储结构方式之邻接表详解
MCU内部DataFlash的特点原理揭秘
电感和磁珠的区别
TDA2030A音频功放及应用
使用最新的机器学习技术进行恶性肿瘤治疗，可以缓解患者在治疗中的痛苦
苏州洲际酒店，使用智能机器人「润」做服务员，会迎宾、送茶等服务
工业测量中的噪声干扰问题
浙江萧山首个内河智能岸电系统在江顺建材码头正式投入使用
基于软件无线电中频接收系统的设计方案
谷歌量子计算机新突破 可几秒内完成47年的任务
先楫半导体发布多个系列高性能微控制器产品
数字化施工引领基础设施建设新潮流
我国IPv6规模部署加速,2025年完成向下一代互联网的平滑演进升级
如何运用数字I/O来保护继电器
关于加速度传感器7102A-0100的几种应用