您好,欢迎来到独旅网。
搜索
您的当前位置:首页数据结构:邻接表

数据结构:邻接表

来源:独旅网
数据结构:邻接表

之前我看了很久都没有搞明⽩邻接表,现在终于差不多搞懂了,特此记录。那么,邻接表是什么呢?邻接表嘛,就是邻接的表。其实邻接表不好理解,主要是开的数组⽐较多,容易弄混,这⼀分钟好像弄懂了,下⼀分钟就不知如何下⼿了。那么接下来:

每⼀个数组的作⽤

head[点的序号] = 从它出发的最后⼀次输⼊的边的编号from[边的序号] = 边的起点;to[边的序号] = 边的终点;

nxt[边的序号] = 输⼊的上⼀个从这条边的出发点出发的边的编号;edge[边的序号] = 边的权值

ATTENTION!

next是保留字!

当然也可以使⽤结构体。

其中除了head[],数组的下标全部都是边⽽不是点!from[]和to[]分别是起点和终点(经常可以不⽤from[]);

有的书上的ver[](如《算法竞赛进阶指南》)就是这⾥的to[]。

add()函数

使⽤邻接表存图的时候,⽤到的add()函数:

void add(int x, int y, int z) {

to[++tot] = y, edge[tot] = z; //edge为边的权值,可视情况⽽⽤ nxt[tot] = head[x], head[x] = tot;}

好好理解⼀下,反正我⼀开始就是卡在“每⼀个数组的作⽤”这⾥。

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- dcrkj.com 版权所有 赣ICP备2024042791号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务